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.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
Given target =
3
, return true
.public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0)
return false;
int x = 0;
int y = matrix[0].length -1;
while(x >=0 && y >=0 && x< matrix.length){
if(matrix[x][y] == target)
return true;
else if(matrix[x][y] > target){
y--;
}else{
x++;
}
}
return false;
}
}
Solution2: O(log(m)+log(n))
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix==null || matrix.length==0 || matrix[0].length==0)
return false;
int start = 0;
int end = matrix.length*matrix[0].length-1;
while(start<=end){
int mid=(start+end)/2;
int x=mid/matrix[0].length;
int y=mid%matrix[0].length;
if(matrix[x][y]==target)
return true;
if(matrix[x][y]<target){
start=mid+1;
}else{
end=mid-1;
}
}
return false;
}
}
Key Concept: From right top to search
沒有留言:
張貼留言