题目描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
思路
思路一: 对二维数组进行遍历看是否存在查询的值,复杂度$O(n*m)$,代码挺简单的不在实现了。
思路二: 因为二维数组每一行都是从左到右递增的,所以把每一行看作有序递增数组,利用二分查找,通过遍历每一行查找得到答案,复杂度$O(nlog(m))$。
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;
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;
}
};