NC29:矩阵查找
矩阵查找
http://www.nowcoder.com/questionTerminal/5145394607ea4c5f8b25755718bfddba
解法1:从右上角开始找,左边的都是比它小的,下边的都是比它大的。
- 如果当前元素等于target,那么说明找到了,返回true;
- 如果当前元素大于target,那么当前元素下面的一定都比target大,所以左移;
- 如果当前元素小于target,那么当前元素左面的一定都比target小,所以下移;
- 如果最后没返回true,则返回false。
时间复杂度:O( m + n ): m为矩阵的行数,n为矩阵的列数public static boolean Find(int[][] array,int target){ int row=0; int col=array[0].length-1; while(row<array.length && col>=0){//判断停止的条件 if(array[row][col]==target){ return true; } else if(array[row][col]<target){ row++;//A<target说明要向下寻找 } else{ col--;//A>target说明要向左寻找; } } return false; }
解法2:二分查找
public boolean searchMatrix (int[][] matrix, int target) { // write code here if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; int m = matrix.length; int n = matrix[0].length; int start = 0,end = m*n-1; while(start <= end){ int mid = (start+end)/2; int val = matrix[mid/n][mid%n]; if(val < target){ start = mid+1; }else if (val > target){ end = mid-1; }else{ return true; } } return false; }
名企高频面试算法题解 文章被收录于专栏
牛客题霸 - 程序员面试高频题 - 题解