来自Leetcode第240题搜索二维矩阵II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下：
给定 target = 5，返回 true。
给定 target = 20，返回 false。
左下/右上遍历
数组从左到右和从上到下都是升序的，如果从右上角出发开始遍历呢？
会发现每次都是向左数字会变小，向下数字会变大，有点和二分查找树相似。二分查找树的话，是向左数字变小，向右数字变大。
所以我们可以把 target 和当前值比较。
- 如果
target 的值大于当前值，那么就向下走。
- 如果
target 的值小于当前值，那么就向左走。
- 如果相等的话，直接返回
true 。
也可以换个角度思考。
如果 target 的值小于当前值，也就意味着当前值所在的列肯定不会存在 target 了，可以把当前列去掉，从新的右上角的值开始遍历。
同理，如果 target 的值大于当前值，也就意味着当前值所在的行肯定不会存在 target 了，可以把当前行去掉，从新的右上角的值开始遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0){
return false;
}
int m = matrix.length;
int n = matrix[0].length;
int i = 0;
int j = n - 1;
while(i<m && j>= 0){
if (matrix[i][j] > target){
j--;
}else if (matrix[i][j] < target){
i++;
}else {
return true;
}
}
return false;
}
|
遍历二分
对每一行都做一次二分查找，来自
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) {
return false;
}
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][0] > target) {
break;
}
if(matrix[i][matrix[i].length - 1] < target){
continue;
}
int col = binarySearch(matrix[i], target);
if (col != -1) {
return true;
}
}
return false;
}
private int binarySearch(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while (start <= end) {
int mid = (start + end) >>> 1;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
|