这道题目我一开始想的是缩小二维数组的范围,就是取出第一行的第一个大于target的下标
和第一列第一个大于target的下标
然后在这个更小的矩阵里进行遍历搜索,最后也勉强ac了
第二种方法就是寻找左上角的值,因为观察整个二维数组只有最外层的一行和最外层的一列存在单调的递增关系,其他的行列是不满足这个条件的,正是利用了这一点,使得时间复杂度降到了线性
算法1
(暴力枚举) $O(n^2)$
时间复杂度
C++ 代码
class Solution {
public:
bool searchArray(vector<vector<int>> array, int target) {
int len1 = array.size();
if(len1 == 0) return false;
int len2 = array[0].size();
int left = len2,bottom = len1;
for(int i = 0;i<len2;i++){
if(array[0][i]>target){
left = i;
break;
}
}
for(int i = 0;i<len1;i++){
if(array[i][0]>target){
bottom = i;
break;
}
}
for(int i = 0;i<bottom;i++){
for(int j = 0;j<left;j++){
if(array[i][j] == target)
return true;
}
}
return false;
}
};
算法2
(思维法) $O(n)$
C++ 代码
class Solution {
public:
bool searchArray(vector<vector<int>> array, int target) {
int len_y = array.size();
if(len_y == 0) return false;
int len_x = array[0].size();
int i = 0;
int j = len_x -1;
while(i < len_y && j >=0 ){
if(array[i][j] == target) return true;
if(array[i][j] >target)//如果左上角的值大于目标值,舍去最左的列
j--;
else i++;
}
return false;
}
};