ava lin number ron 时间复杂度 二分查找 [] arr 元素
写出一个高效的算法来搜索 m × n 矩阵中的值.
这个矩阵具有以下特性:
每行中的整数从左到右是排序的.
每行的第一个数大于上一行的最后一个整数.
易错点:1:二维数组怎么判定为空 array.length==02:二维数组怎么取它的列数 a[0].length,行数 a.length3:while 循环中的两个条件为什么是逻辑与
两种思路一种是:
把每一行看成有序递增的数组,
利用二分查找,
通过遍历每一行得到答案,
时间复杂度是nlogn
另外一种思路是:
public class Solution {
public boolean Find(int [][] array,int target) {
for(int i=0
;i<array.length;i++){
int low=0;
int
high = array[i].length -
1;
while(low<=high){
int mid=(low+high)/2;
if
(target > array[i][mid])
low=mid+1;
else if
(target < array[i][mid])
high=mid-1;
else
return true;
}
}
return false;
}
}
利用二维数组由上到下,由左到右递增的规律,
那么选取右上角或者左下角的元素a[row][col]与target进行比较,
当target小于元素a[row][col]时,那么target必定在元素a所在行的左边,
即 col--;
当target大于元素a[row][col]时,那么target必定在元素a所在列的下边,
即 row++;
28. 搜索二维矩阵
public class Solution {
public boolean Find(int [][] array,int target) {
int row=0;
int col=array[0].length-1;
while(row<=array.length-1&&col>=0){
if
(target == array[row][col])
return true;
else if
(target > array[row][col])
row++;
else
col--;
}
return false;
}
}
来源: http://www.bubuko.com/infodetail-2462743.html