剑指office--------二维数组的查找

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路1：暴力遍历

 1 class Solution {
 2 public:
 3     int add(int target, vector<vector<int> > array,int x,int pos){
 4         while (1){
 5             if (array[x].size()<=pos)    return pos-1;
 6             if (array[x][pos]==target){
 7                 return -1;
 8             }
 9             if (array[x][pos]<target){
10                 pos++;
11                 continue;
12             }
13             else    return pos;
14         }
15 
16         
17     }
18     int sub(int target, vector<vector<int> > array,int x,int pos){
19         while (1){
20             if (pos<0)    return 0;
21             if (array[x][pos]==target)    return -1;
22             if (array[x][pos]>target){
23                 pos--;
24                 continue;
25             }
26             else     return pos;
27         }
28     }
29     bool Find(int target, vector<vector<int> > array) {
30         if (array.size()==0||array[0].size()==0)    return false;
31         bool flag=false;
32         int rows=array.size(),col=array[0].size();
33         for (int i=0,pos=0;i<rows;i++){
34             if (array[i][pos]==target)    return true;
35             else if (array[i][pos]<target){
36                 pos=add(target,array,i,pos);
37             }
38             else    pos=sub(target,array,i,pos);
39             if (pos==-1)    return true;
40         }
41         return flag;
42     }
43 };

思路2：当找到一个数字大于待查找的数字时，那么可以将矩阵进行分割，如图

此处选择了右上角做判定

 1 class Solution {
 2 public:
 3     bool Find(int target, vector<vector<int> > array) {
 4         if (array.size()==0||array[0].size()==0)    return false;
 5         int rows=0,col=array[0].size()-1;
 6         int temp=array.size();
 7         while (rows<temp&&col>=0){
 8             if (array[rows][col]==target)    return true;
 9             if (array[rows][col]>target)    col--;
10             else    rows++;
11         }
12         return false;
13     }
14 };

n*m矩阵

时间复杂度：O（n+m）

空间复杂度：O（1）