算法1
(暴力枚举) $O(n^2)$
随机优化了一下,时间复杂度应该nn/43左右
java 代码
class Solution {
public boolean searchArray(int[][] array, int target) {
int m=0,m1=0;
if(array.length!=0){
m1=array[0].length;
}
for (int i=0;i<array.length;i++){
for (int j=0;j<m1;j++){
if (array[i][j]==target){
return true;
}
else if (array[i][j]>target){
m1=j;
break;
}
}
}
return false;
}
}
算法2
从右上角开始枚举
时间复杂度(m+n)
java 代码
class Solution {
public boolean searchArray(int[][] array, int target) {
int l=0,r=0;
if (array.length!=0){
r=array[0].length-1;
}
while (l>=0&&l<array.length&&r>=0&&r<array[0].length){
if (array[l][r]==target){
return true;
}
else if (array[l][r]>target){
r--;
}
else {
l++;
}
}
return false;
}
}