题目：
搜索二维矩阵
写出一个高效的算法来搜索 m × n矩阵中的值。
这个矩阵具有以下特性：
- 每行中的整数从左到右是排序的。
- 每行的第一个数大于上一行的最后一个整数。
样例
考虑下列矩阵：
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
给出 target = 3，返回 true
挑战
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;
}
}