题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路
思路一： 对二维数组进行遍历看是否存在查询的值，复杂度$O(n*m)$，代码挺简单的不在实现了。
思路二： 因为二维数组每一行都是从左到右递增的，所以把每一行看作有序递增数组，利用二分查找，通过遍历每一行查找得到答案，复杂度$O(nlog(m))$。
Code
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int n=array.size(),m=array[0].size();
for(int i=0;i<n;++i){
int id=lower_bound(array[i].begin(),array[i].end(),target)-array[i].begin();
if(id<m&&array[i][id]==target)return true;
}
return false;
}
};思路三： 因为二维数组每行从左到右递增，每列从上到下递增。这样我们可以从右上角开始查找，如果当前元素大于所查找的值，根据列从上到下递增，则可以将这一列都剔除，所以对列指针左移。如果当前元素小于所查找的值，根据行从左到有递增，则可以将该一行都剔除，所以行指正下移。复杂度$O(n+m)$，可能因为牛客这题数据没有大数据，所以思路二耗时可能比思路三少。
例如：
对于二维数组：
| 1 | 2 | 8 | 9 |
|---|---|---|---|
| 2 | 4 | 9 | 12 |
| 4 | 7 | 10 | 13 |
| 6 | 8 | 11 | 15 |
如果在一个二维数组中找到数字10，则返回true，如果没有找到，则返回false。
查找过程如下：
- 初始化行列指针 i=0,j=3;
- 9小于10，下一次只需在9下边区域查找，++i;
- 12大于10，下一次只需要在12的左边区域查找，--j;
- 9大于10，下一次只需要在9的下边区域查找，++i;
- 发现找到10，返回true;
Code
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int n=array.size(),m=array[0].size();
int i=0,j=m-1;
while(j>=0&&i<n){
if(array[i][j]>target)--j;
else if(array[i][j]<target)i++;
if(j>=0&&i<n&&array[i][j]==target)return true;
}
return false;
}
};