开源地址
为了便于大家学习，所有实现均已开源。欢迎 fork + star~
240. 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。
该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1：
输入：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]], target = 5 输出：true
示例 2：
输入：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]], target = 20 输出：false
提示：
m == matrix.length n == matrix[i].length 1 <= n, m <= 300 -10^9 <= matrix[i][j] <= 10^9 每行的所有元素从左到右升序排列 每列的所有元素从上到下升序排列 -10^9 <= target <= 10^9
v1-暴力
思路
直接全遍历
实现
public boolean searchMatrix(int[][] matrix, int target) {
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix.length; j++) {
if(matrix[i][j] == target) {
return true;
}
}
}
return false;
}
效果
12ms 击败 8.67%
复杂度
TC O(m*n)
反思
看到有序，看到查找，应该想到二分法。
v2-单边的二分法
思路
我们最容易想到的是，是在某一行、某一列加一下对应的二分查找信息。
实现
public boolean searchMatrix(int[][] matrix, int target) {
for(int i = 0; i < matrix.length; i++) {
int[] nums = matrix[i];
int index = binarySearch(nums, target);
if(index > -1) {
return true;
}
}
return false;
}
// 返回对应的位置
private int binarySearch(int[] nums, int target) {
// 提前判断这一行是否可能存在
if(target < nums[0] || target > nums[nums.length-1]) {
return -1;
}
int left = 0;
int right = nums.length-1;
// 要等于吗？
while (left <= right) {
int mid = left + (right-left) / 2;
if(nums[mid] == target) {
return mid;
} else if(nums[mid] > target ) {
// 太大，那么就去左边
right = mid-1;
} else {
// 太小，在右边
left = mid+1;
}
}
return -1;
}
效果
7ms 击败 38.80%
复杂度
TC: O(m * log n)
略有提升。
反思
但是因为行+列都是有序的。
有没有办法可以同时加速呢？
v3-z字抖动
思路
对于一位有序，我们左右移动，来找到合适的位置。因为有序二分可以尽可能的排除掉不合适的数字。
那么推广到二维呢？
其实和二分类似，只不过我们一次移动一步。
例子
以一个示例矩阵举例：
matrix = [
[ 1, 4, 7, 11],
[ 2, 5, 8, 12],
[ 3, 6, 9, 16],
[10, 13, 14, 17]
]
想法推导思路：
- 观察二维有序性 → 行和列都是递增的
-
尝试从某个“边界角落”开始：
- 左上角？两个方向都增大 → 无法决策 ❌
- 右下角？两个方向都减小 → 也不适合 ❌
- 左下角？上是减小，右是增大 → 可行 ✅
- 右上角？左是减小，下是增大 → 最直观 ✅✅
- 每次移动能排除一行或一列，复杂度降到 O(m+n)
右上角出发
假设我们从 右上角 matrix[0][n-1] = 11 开始，看看四周的数据如何变化：
🎯 如何根据比较结果移动？
假设 target = 9，从 11 开始：
- 11 > 9，太大了 → 往左（列–）
- 到了 7，7 < 9，太小了 → 往下（行++）
- 到了 8，还是小 → 行++
- 到了 9，找到了 ✅
✅ 总结出策略：
从右上角开始，每次根据当前值和 target 的比较，只需要做一个决策：
- 如果当前值 > target → 往左（col–）
- 如果当前值 < target → 往下（row++）
- 如果相等 → 找到了！
实现
我们把二分，改成了从右上角来一步步移动
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
// 从右上角开始
int row = 0;
int col = n - 1;
// 往左走，变小 往下走，变大
// 要求：左边 >= 0 下边 < m
while (row < m && col >= 0) {
int cur = matrix[row][col];
if(cur == target) {
return true;
}
if(cur > target) {
col--;
}
if(cur < target) {
row++;
}
}
return false;
}
效果
6ms 击败 99.99%
复杂度
O(m + n) 最优，空间 O(1)，适合面试
反思
前提是要能想到。
小结
希望本文对你有帮助，如果有其他想法的话，也可以评论区和大家分享哦。
各位极客的点赞收藏转发，是老马持续写作的最大动力！
感兴趣的小伙伴可以关注一波，精彩内容，不容错过。
