https://leetcode.com/problems/search-a-2d-matrix-ii/
// 从左下角开始，尝试不断向右边走
// 右边走不动了，就向下面走，直到出边界
public boolean searchMatrix(int[][] matrix, int target) {
int row = matrix.length;
if (row == 0) {
return false;
}
int col = matrix[0].length;
// 从左下角开始搜索
int x = row - 1;
int y = 0;
// 每次考虑向上走
while (x >= 0) {
// 向上走之前，尽量向右边走
while (y < col && matrix[x][y] < target) {
y++;
}
if (y < col && matrix[x][y] == target) {
return true;
}
x--;
}
return false;
}
https://leetcode.com/problems/search-a-2d-matrix-ii/discuss/66140/My-concise-O(m%2Bn)-Java-solution
public boolean searchMatrix(int[][] matrix, int target) { if(matrix == null || matrix.length < 1 || matrix[0].length <1) { return false; } int col = matrix[0].length-1; int row = 0; while(col >= 0 && row <= matrix.length-1) { if(target == matrix[row][col]) { return true; } else if(target < matrix[row][col]) { col--; } else if(target > matrix[row][col]) { row++; } } return false; }
http://bookshadow.com/weblog/2015/07/23/leetcode-search-2d-matrix-ii/
http://www.jyuan92.com/blog/leetcode-search-a-2d-matrix-ii/
From book - cracking code
Coordinate findElement(int[][] matrix, Coordinate or1g1n, Coordinate dest, int x){
if (!origin.inbounds (matrix) || ! dest.inbounds(matrix)) {
return null;
}
if (matrix[origin.row][origin.column]
return origin;
} else if (!origin.isBefore(dest)) {
return null;
}
/* Set start to start of diagonal and end to the end of the diagonal. Since the
* grid may not be square, the end of the diagonal may not equal dest. */
Coordinate start= (Coordinate) origin.clone();
int diagDist = Math.min(dest.row - origin.row, dest.column - origin.column);
Coordinate end= new Coordinate(start.row + diagDist, start.column + diagDist);
Coordinate p = new Coordinate(0, 0);
/* Do binary search on the diagonal, looking for the first element> x */
while (start.isBefore(end)) {
p.setToAverage(start, end);
if (x > matrix[p.row][p.column]) {
start.row = p.row + 1;
start.column = p.column + 1;
} else {
end.row = p.row - 1;
end.column = p.column - 1;
}
}
/* Split the grid into quadrants. Search the bottom left and the top right. */
return partitionAndSearch(matrix, origin, dest, start, x);
}
Coordinate partitionAndSearch(int[][] matrix, Coordinate origin, Coordinate dest,
Coordinate pivot, int x) {
Coordinate lowerLeftOrigin = new Coordinate(pivot.row, origin.column);
Coordinate lowerLeftDest = new Coordinate(dest.row, pivot.column - 1);
Coordinate upperRightOrigin = new Coordinate(origin.row, pivot.column);
coordinate upperRightDest = new Coordinate(pivot.row - 1, dest.column);
Coordinate lowerLeft = findElement(matrix, lowerLeftOrigin, lowerLeftDest, x);
if (lowerleft == null) {
return findElement(matrix, upperRightOrigin, upperRightDest, x);
}
return lowerleft;
}
Coordinate findElement(int[][] matrix, int x) {
Coordinate origin = new Coordinate(0, 0);
coordinate dest = new Coordinate(matrix.length - 1, matrix[0].length - 1);
return findElement(matrix, origin, dest, x);
}
public class Coordinate implements Cloneable {
public int row, column;
public Coordinate(int r, int c) {
row = r;
column = c;
}
public boolean inbounds(int[][] matrix) {
return row >= 0 && column >= 0 &&
row< matrix.length && column< matrix[0].length;
}
public boolean isBefore(Coordinate p) {
return row<= p.row && column<= p.column;
}
public Object clone() {
return new Coordinate(row, column);
}
public void setToAverage(Coordinate min, Coordinate max) {
row = (min.row + max.row) / 2;
column = (min.column + max.column)/ 2;
}
}
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 in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following matrix:
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
Given target =
5, return true.- Time Complexity: O(m + n)
Given target =
20, return false.
public boolean searchMatrix(int[][] matrix, int target) {
int row = matrix.length;
if (row == 0) {
return false;
}
int col = matrix[0].length;
// 从左下角开始搜索
int x = row - 1;
int y = 0;
// 每次考虑向右边走
while (y < col) {
// 向右边走之前，尽量向上走
while (x >= 0 && matrix[x][y] > target) {
x--;
}
// 走不动了，再向右边走
if (x >= 0 && matrix[x][y] == target) {
return true;
}
y++;
}
return false;
}
public boolean searchMatrix(int[][] matrix, int target) {
int row = matrix.length;
if (row == 0) {
return false;
}
int col = matrix[0].length;
// 从右上角开始搜索
int x = 0;
int y = col - 1;
// 每次考虑向下走
while (x < row) {
// 向下走之前，尽量向左边走
while (y >= 0 && matrix[x][y] > target) {
y--;
}
if (y >= 0 && matrix[x][y] == target) {
return true;
}
x++;
}
return false;
}
public boolean searchMatrix(int[][] matrix, int target) { if(matrix == null || matrix.length < 1 || matrix[0].length <1) { return false; } int col = matrix[0].length-1; int row = 0; while(col >= 0 && row <= matrix.length-1) { if(target == matrix[row][col]) { return true; } else if(target < matrix[row][col]) { col--; } else if(target > matrix[row][col]) { row++; } } return false; }
it's also OK to search from the bottom-left point. Just check the code below.
public static boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length < 1 || matrix[0].length < 1)
return false;
int col = 0;
int row = matrix.length - 1;
while (col <= matrix[0].length - 1 && row >= 0) {
if (target == matrix[row][col])
return true;
else if (target < matrix[row][col])
row--;
else if (target > matrix[row][col])
col++;
}
return false;
}http://bookshadow.com/weblog/2015/07/23/leetcode-search-2d-matrix-ii/
O(m * logn)解法：循环枚举行，二分查找列
def searchMatrix(self, matrix, target): y = len(matrix[0]) - 1 def binSearch(nums, low, high): while low <= high: mid = (low + high) / 2 if nums[mid] > target: high = mid - 1 else: low = mid + 1 return high for x in range(len(matrix)): y = binSearch(matrix[x], 0, y) if matrix[x][y] == target: return True return FalseO(n ^ 1.58)解法：
参考：https://leetcode.com/discuss/47528/c-with-o-m-n-complexity
分治法，以矩形中点为基准，将矩阵拆分成左上，左下，右上，右下四个区域
若中点值 < 目标值，则舍弃左上区域，从其余三个区域再行查找
若中点值 > 目标值，则舍弃右下区域，从其余三个区域再行查找
时间复杂度递推式：
public boolean searchMatrix(int[][] matrix, int target) {
int n=matrix.length, m=matrix[0].length;
return helper(matrix,0,n-1,0,m-1,target);
}
boolean helper(int[][] matrix, int rowStart, int rowEnd, int colStart, int colEnd, int target ){
if(rowStart>rowEnd||colStart>colEnd){
return false;
}
int rm=(rowStart+rowEnd)/2, cm=(colStart+colEnd)/2;
if(matrix[rm][cm]== target){
return true;
}
else if(matrix[rm][cm] >target){
return helper(matrix, rowStart, rm-1,colStart, cm-1,target)||
helper(matrix, rm, rowEnd, colStart,cm-1,target) ||
helper(matrix, rowStart, rm-1,cm, colEnd,target);
}
else{
return helper(matrix, rm+1, rowEnd, cm+1,colEnd,target)||
helper(matrix, rm+1, rowEnd, colStart,cm,target) ||
helper(matrix, rowStart, rm,cm+1, colEnd,target);
}T(n) = 3T(n/2) + chttp://www.jyuan92.com/blog/leetcode-search-a-2d-matrix-ii/
Divide-Conquer，Based on the mid of the matrix, divide the whole matrix into four parts: left-top, left-bottom, right-top, right-bottom
- If the mid is smaller than target, abandon the left-top area, recursion from the other three areas.
- If the mid is larger than target, abandon the right-bottom area, recursion from the other three ares.
- Time Complexity formula：T(n) = 3T(n/2) + c
public boolean searchMatrixImprove(int[][] matrix, int target) {
if (null == matrix || matrix.length == 0) {
return false;
}
return helper(matrix, 0, matrix.length - 1, 0, matrix[0].length - 1, target);
}
private boolean helper(int[][] matrix, int rowStart, int rowEnd, int colStart, int colEnd, int target) {
if (rowStart > rowEnd || colStart > colEnd) {
return false;
}
int rowMid = rowStart + (rowEnd - rowStart) / 2;
int colMid = colStart + (colEnd - colStart) / 2;
if (matrix[rowMid][colMid] == target) {
return true;
} else if (matrix[rowMid][colMid] > target) {
return helper(matrix, rowStart, rowMid - 1, colStart, colMid - 1, target) ||
helper(matrix, rowMid, rowEnd, colStart, colMid - 1, target) ||
helper(matrix, rowStart, rowMid - 1, colMid, colEnd, target);
} else {
return helper(matrix, rowMid + 1, rowEnd, colMid + 1, colEnd, target) ||
helper(matrix, rowMid + 1, rowEnd, colStart, colMid, target) ||
helper(matrix, rowStart, rowMid, colMid + 1, colEnd, target);
}
}
https://discuss.leetcode.com/topic/33240/java-an-easy-to-understand-divide-and-conquer-method
The coding seems to be much more complex than those smart methods such as this one, but the idea behind is actually quite straightforward.
Unfortunately, it is not as fast as the smart ones.
First, we divide the matrix into four quarters as shown below:
zone 1 zone 2
* * * * | * * * *
* * * * | * * * *
* * * * | * * * *
* * * * | * * * *
-----------------------
* * * * | * * * *
* * * * | * * * *
* * * * | * * * *
* * * * | * * * *
zone 3 zone 4
We then compare the element in the center of the matrix with the target. There are three possibilities:
- center < target. In this case, we discard zone 1 because all elements in zone 1 are less than target.
- center > target. In this case, we discard zone 4.
- center == target. return true.
For time complexity, if the matrix is a square matrix of size
nxn, then for the worst case,T(nxn) = 3T(n/2 x n/2)
which makes
T(nxn) = O(n^log3)From book - cracking code
Coordinate findElement(int[][] matrix, Coordinate or1g1n, Coordinate dest, int x){
if (!origin.inbounds (matrix) || ! dest.inbounds(matrix)) {
return null;
}
if (matrix[origin.row][origin.column]
return origin;
} else if (!origin.isBefore(dest)) {
return null;
}
/* Set start to start of diagonal and end to the end of the diagonal. Since the
* grid may not be square, the end of the diagonal may not equal dest. */
Coordinate start= (Coordinate) origin.clone();
int diagDist = Math.min(dest.row - origin.row, dest.column - origin.column);
Coordinate end= new Coordinate(start.row + diagDist, start.column + diagDist);
Coordinate p = new Coordinate(0, 0);
/* Do binary search on the diagonal, looking for the first element> x */
while (start.isBefore(end)) {
p.setToAverage(start, end);
if (x > matrix[p.row][p.column]) {
start.row = p.row + 1;
start.column = p.column + 1;
} else {
end.row = p.row - 1;
end.column = p.column - 1;
}
}
/* Split the grid into quadrants. Search the bottom left and the top right. */
return partitionAndSearch(matrix, origin, dest, start, x);
}
Coordinate partitionAndSearch(int[][] matrix, Coordinate origin, Coordinate dest,
Coordinate pivot, int x) {
Coordinate lowerLeftOrigin = new Coordinate(pivot.row, origin.column);
Coordinate lowerLeftDest = new Coordinate(dest.row, pivot.column - 1);
Coordinate upperRightOrigin = new Coordinate(origin.row, pivot.column);
coordinate upperRightDest = new Coordinate(pivot.row - 1, dest.column);
Coordinate lowerLeft = findElement(matrix, lowerLeftOrigin, lowerLeftDest, x);
if (lowerleft == null) {
return findElement(matrix, upperRightOrigin, upperRightDest, x);
}
return lowerleft;
}
Coordinate findElement(int[][] matrix, int x) {
Coordinate origin = new Coordinate(0, 0);
coordinate dest = new Coordinate(matrix.length - 1, matrix[0].length - 1);
return findElement(matrix, origin, dest, x);
}
public class Coordinate implements Cloneable {
public int row, column;
public Coordinate(int r, int c) {
row = r;
column = c;
}
public boolean inbounds(int[][] matrix) {
return row >= 0 && column >= 0 &&
row< matrix.length && column< matrix[0].length;
}
public boolean isBefore(Coordinate p) {
return row<= p.row && column<= p.column;
}
public Object clone() {
return new Coordinate(row, column);
}
public void setToAverage(Coordinate min, Coordinate max) {
row = (min.row + max.row) / 2;
column = (min.column + max.column)/ 2;
}
}
