Difficulty:medium
More:【目录】LeetCode Java实现
Description
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Example 1:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Example 2:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false
Intuition
regard the matrix as an array, and then use binary search.
matrix[x][y]=array[x*cols+y]
array[m]=matrix[m/cols][m%cols]
Solution
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix==null || matrix.length<=0 || matrix[0].length<=0)
return false;
int rows=matrix.length; //行数
int cols=matrix[0].length; //列数
int low=0;
int high=rows*cols-1;
while(low<=high){
int mid=(low+high)/2;
if(matrix[mid/cols][mid%cols]==target){
return true;
}else if(matrix[mid/cols][mid%cols]>target){
high=mid-1;
}else if(matrix[mid/cols][mid%cols]<target){
low=mid+1;
}
}
return false;
}
Complexity
Time complexity : O(log(n*m))
Space complexity : O(1)
What I've learned
1. Ought to have a good command of the change between array <=> matrix, especially the change of their indexes
More:【目录】LeetCode Java实现