题目：
搜索二维矩阵
写出一个高效的算法来搜索 m × n矩阵中的值。
这个矩阵具有以下特性：
- 每行中的整数从左到右是排序的。
- 每行的第一个数大于上一行的最后一个整数。
样例
考虑下列矩阵：
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
给出 target = 3，返回 true
挑战
View Code
View Code
View Code
View Code
O(log(n) + log(m)) 时间复杂度
解题：
更新730
直接二分查找
public boolean searchMatrix(int[][] A, int target) { // write your code here if(A == null || A.length == 0 || A[0].length ==0) return false; int row = A.length; int col = A[0].length; int len = row * col; int left = 0; int right = len-1 ;// while(left <= right){ int mid = left + (right - left)/2; int x = A[mid/col][mid%col]; if(x==target){ return true; }else if(x>target){ right = mid-1; }else{ left = mid+1; } } return false; }
1.最简单的方法就是遍历整个矩阵，时间复杂度：O(log(mn)),这个应该等于O(long(n)+log(m))
2.题目给的矩阵是有序矩阵，先按照最后一列二分查找，确定列，再二分确定行，时间复杂度O(log(m)) + O(log(n)),哦，哦，哦，题目的挑战可能是搞错了。。。
1.暴力
Java程序：
public class Solution { /** * @param matrix, a list of lists of integers * @param target, an integer * @return a boolean, indicate whether matrix contains target */ public boolean searchMatrix(int[][] matrix, int target) { // write your code here 二分查找 if(matrix==null) return false; int m = matrix.length; if(m==0) return false; int n = matrix[0].length; for(int i=0;i<m;i++){ for(int j=0;j<n;j++) if(matrix[i][j]==target) return true; } return false; } }
总耗时: 1571 ms
Python程序：
class Solution: """ @param matrix, a list of lists of integers @param target, an integer @return a boolean, indicate whether matrix contains target """ def searchMatrix(self, matrix, target): # write your code here if matrix==None: return False m = len(matrix) if m==0: return False n = len(matrix[0]) for i in range(m): for j in range(n): if matrix[i][j]==target: return True return False
总耗时: 260 ms
2.二分法
利用二分思想程序，先求所在的行，再求所在的列，搞了好久，边界错了好多次。。。
Java程序：
public class Solution { /** * @param matrix, a list of lists of integers * @param target, an integer * @return a boolean, indicate whether matrix contains target */ public boolean searchMatrix(int[][] matrix, int target) { // write your code here 二分查找 if(matrix==null) return false; int nrow = matrix.length; if(nrow==0) return false; int ncol = matrix[0].length; // 行 nrow //列 ncol int row = rowbinSearch(matrix,0,nrow-1,ncol,target); int col = colbinSearch(matrix,0,ncol-1,row,target); if(col!=-1) return true; return false; } // 找出所在的行 private int rowbinSearch(int[][] matrix,int left,int right,int ncol,int target){ //矩阵matrix ，二分的两个界：left、right，矩阵的最后一列ncol,目标值target int median = (left + right)/2; int row = median; if(left==right) return left; if(matrix[left][ncol-1]<=target && matrix[left+1][ncol-1]>target) return left; if(matrix[median][ncol-1]>= target && matrix[median][0]<=target) return median; if(matrix[median][ncol-1]<target) row = rowbinSearch(matrix,median+1,right,ncol,target); else row = rowbinSearch(matrix,left,median-1,ncol,target); return row; } // 找出所在的列 private int colbinSearch(int[][] matrix,int left,int right,int row,int target){ //矩阵matrix ，二分的两个界：left、right，target所在的行： row,目标值target int median = (left + right)/2; int col = median; if(left>right) return -1; if(left==right && matrix[row][left]!=target) return -1; if(matrix[row][median]==target) return median; if(matrix[row][median]<target) col = colbinSearch(matrix,median+1,right,row,target); else col = colbinSearch(matrix,left,median-1,row,target); return col; } }
总耗时: 2246 ms
3.暴力2.0
九章算法中看到的，给的Java程序利用二分法，但是没有用递归，给的Python程序，没有明显的用到矩阵变量，但是通过商和余数确定所在的行和列
Python程序：
class Solution: """ @param matrix, a list of lists of integers @param target, an integer @return a boolean, indicate whether matrix contains target """ def searchMatrix(self, matrix, target): # write your code here if len(matrix)==0: return False n,m=len(matrix),len(matrix[0]) start,end = 0,n*m-1 while start+1< end: mid = (start + end)/2 x,y = mid/m,mid%m if matrix[x][y]<target: start = mid else: end = mid x,y = start/m,start%m if matrix[x][y]==target: return True x,y = end/m,end%m if matrix[x][y] == target: return True return False
总耗时: 261 ms
更新
可每次去除一行或者一列，这样划分的形式解题
时间复杂度O(M+N)
public class Solution { /** * @param matrix, a list of lists of integers * @param target, an integer * @return a boolean, indicate whether matrix contains target */ public boolean searchMatrix(int[][] matrix, int target) { // write your code here if(matrix == null || matrix.length == 0 || matrix[0].length ==0) return false; int row = 0; int col = matrix[0].length-1; return searchMatrix(matrix,row,col,target); } // 右上角开始是找 public boolean searchMatrix(int[][] mat,int row,int col,int target){ if(row<0 || row>= mat.length || col<0 || col>mat[0].length) return false; if(mat[row][col] == target) return true; else if(mat[row][col] < target) return searchMatrix(mat,row+1,col,target); else return searchMatrix(mat,row,col-1,target); } }
该成递归形式
注意下面的两个while循环
public class Solution { /** * @param matrix, a list of lists of integers * @param target, an integer * @return a boolean, indicate whether matrix contains target */ public boolean searchMatrix(int[][] matrix, int target) { // write your code here if(matrix == null || matrix.length == 0 || matrix[0].length ==0) return false; int row = 0; int col = matrix[0].length-1; // 注意下面两个while 循环 row col 都要判断的 while(row< matrix.length&& col>=0){ while(row< matrix.length&& col>=0){ if (matrix[row][col] == target){ return true; }else if(matrix[row][col] > target){ col--; }else{ row++; } } } return false; } }