题目描述
编写一个高效的算法来搜索 $m\times n$ 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
样例
现有矩阵 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
。
给定 target = 20
,返回 false
。
算法1
(二分) $O((m + n)\log m\times n)$
算法的思路类似于LeetCode 34. 找相同元素出现的起始位置 ,这里拓展成了二维的情况,所以我们分别要搜索出上下左右这四个边界来找到矩阵中等于target
的区域:
第一步:
-
在上边界
up
上二分出最后一个小于等于x
的右边界right
,因为显然该点右边的元素都会严格的大于x
。注意这里不能在上边界二分出左边界left
,因为左边有可能会有大于或等于x
的元素,这点看样例就能明白,如果我们一开始在上边界搜索左边界,那么会将左边界移动到第一行7
的位置,就将target
排除出去了。 -
在
down
上二分出第一个大于等于x
的left
,因为显然左边的元素都会严格的小于x
。
第二步:
-
在
new_right
上二分出第一个大于等于x
的up
,因为显然该点上半部的元素都会严格小于x
。 -
在
new_left
上二分出最后一个小于等于x
的down
,同上
当up down left right
都停止更新的时候说明找到了一片区域都等于x,直接返回true
时间复杂度
每次二分需要$O(\log m \times n)$的复杂度,最多会进行 $k$ 次二分,这里$k = O(m + n)$,因为每次边界都会至少缩短一步,左右和上下边界分别最多缩短 $m$ 和 $n$ 次。
C++ 代码
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int m = matrix.size(), n = matrix[0].size();
int up = 0, down = m - 1, left = 0, right = n - 1;
int l, r;
while (left < right || up < down)
{
int new_left, new_right, new_up, new_down;
l = left, r = right;
while (l < r)
{
int mid = l + r >> 1;
if (matrix[down][mid] < target) l = mid + 1;
else r = mid;
}
new_left = l;
l = left, r = right;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (matrix[up][mid] <= target) l = mid;
else r = mid - 1;
}
new_right = l;
l = up, r = down;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (matrix[mid][new_left] <= target) l = mid;
else r = mid - 1;
}
new_down = l;
l = up, r = down;
while (l < r)
{
int mid = l + r >> 1;
if (matrix[mid][new_right] < target) l = mid + 1;
else r = mid;
}
new_up = l;
if (new_left == left && new_right == right && new_up == up && new_down == down)
return true;
left = new_left, right = new_right;
up = new_up, down = new_down;
}
return matrix[up][left] == target;
}
};