思路:
①二维数组遍历,直至找到目标值,时间复杂度O(n平方),数据规模大,效率低(虽然本题不会超时);
②观察规律,每一行的数从小到大,每一列的数从小到大。若从二位数组矩阵右上角处出发,(辐射覆盖范围是包括它的左边和下面所有数字元素面积),同一行左边的数都小于它,同一列下边的数都大于它,因此可以与目标值target比较,若大于目标值,可以排除同一列的数,若小于目标值,可以排除同一行的数,依据此条件进行从右上角出发处的移动,直至找到target。
Notes:
要进行特判,数组行为空或者列为空时,直接返回false;
从右上角出发点开始移动,在移动过程可能会出现越界,要做处理,越界返回false;
要考虑该二位数组不存在target的情况,知道其终点停止位置;
亦可以从左下角开始移动,但不能从左上角或者右下角开始,举个例子,从左上角处开始,该点小于目标值,有向右向下两种移动方式,无法判别;
代码:
class Solution {
public boolean searchArray(int[][] array, int target) {
if(array.length==0 || array[0].length==0){
return false;
}
int row=0;
int col=array[0].length-1;
while(!(row==array.length-1 && col==0)){
if(array[row][col]==target){
return true;
}
if(array[row][col]>target){
col--;
if(col<0){
return false;
}
}
else{
row++;
if(row>=array.length){
return false;
}
}
}
if(array[row][col]==target){
return true;
}
else{
return false;
}
}
}