05 August 2008
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Example:
Consider the following matrix:
1
2
3
4
5
6
7
[
[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.
Given target = 20, return false.
和上一道题相比，矩阵左右和上下也都是升序排好的，但是上一行最后一个数或多个数不一定小于于下一行的第一个数或多个数。这道题的解法可以从右上角开始(从左下角开始也是可以的)，比较target 和 matrix[row][column]的值。 如果小于target，则该行不可能有此数，所以row++；如果大于target；则该列不可能有此数，所以column–；遇到边界则表明该矩阵不含target。
Time：O(m+n)；Space：O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int row = 0, col = matrix[0].length - 1;//初始化从右上角开始，或者左下角也可以
while (row < matrix.length && col >= 0) {
if (target == matrix[row][col]) {
return true;
} else if (target < matrix[row][col]) {//如果target小于初始右上角的值matrix[row][col]，那么target不会在这一列上，这时候将列的index左移
col--;
} else {//反之如果target大于初始右上角的值matrix[row][col]，那么target不会在这一行上，这时候将row下移
row++;
}
}
return false;
}
}