题目:
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
array: 待查找的二维数组target:查找的数字。查找到返回true,查找不到返回false。
思路: 1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
例如上面的二维数组,因为数组是部分有序的,所以很快会想到用二分或者二叉查找树,如果以9为根节点看的话,整个二维矩阵就是一棵二叉查找树。利用这个思想就可以降低时间复杂度。比如要找的数是7,则从9开始,9>7所以把9所在的列去掉,列指针左移,8>7同样的操作,2<7把2所在行去掉,行指针下移,4<7同样的操作,7==7返回true。这个思路明白了,边界情况稍加考虑代码很容易些出来。当然以6开始也满足二叉查找树的情况,但是左上角和右下角就不满足了。
实现代码:
public class Solution { public boolean Find(int [][] matrix,int t) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; int row = 0; int col = matrix[0].length - 1; //从右上角开始 while(row < matrix.length && col >= 0) { if(matrix[row][col] == t) return true; else if(matrix[row][col] > t) { col --; } else { row ++; } } return false; }}