题目链接:二维数组中的查找
难度:中等
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
数据范围:矩阵的长宽满足0≤n,m≤500,矩阵中的值满足 0≤val≤10^9
进阶:空间复杂度O(1),时间复杂度O(n+m)
比如在下面的二维数组中查找数字7,查找过程如下:
很明显,由于该二维数组上到下递增,左到右递增的特殊性,遍历整个矩阵进行查找不是该题目的意图所在。总结规律我们可以发现:应该从矩阵的右上角或者左下角开始查找。
以右上角为例,首先选取右上角的数字,如果该数字等于要查找的数字,则查找过程结束;如果该数字大于要查找的数字,则说明该列其他元素都大于要查找的数字,便可以删掉该列;如果该数字小于要查找的数字,则说明该行其他元素也都小于要查找的数字,便可以删掉该行。
这样,每一次比较都可以剔除一行或者一列,进而缩小查找范围,时间复杂度为O(n) 。
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
//如果数组为空,则直接返回false
if(matrix==null || matrix.length == 0 ) {
return false;
}
//从右上角开始找
int i=0,j=0;
for(i =0,j=matrix[0].length-1; i<matrix.length && j>=0;) {
if(matrix[i][j] == target) {
return true; //如果找到直接返回true
}
else if(matrix[i][j]>target) { //如果该值大于查找值,跳过该列
j--;
}
else { //如果该值小于查找值,跳过该行
i++;
}
}
return false; //最后记得返回false,不然会报错
}
}