LC 74. 搜索二维矩阵

题目描述

这是 LeetCode 上的 74. 搜索二维矩阵 ,难度为 中等

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1:

1
2
3
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

输出:true

示例 2:

1
2
3
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

输出:false

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -$10^4$ <= matrix[i][j], target <= $10^4$

二分解法(一)

由于二维矩阵固定列的「从上到下」或者固定行的「从左到右」都是升序的。

因此我们可以使用两次二分来定位到目标位置:

  1. 第一次二分:从第 0 列中的「所有行」开始找,找到合适的行 row

  2. 第二次二分:从 row 中「所有列」开始找,找到合适的列 col

代码:

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
class Solution {
public boolean searchMatrix(int[][] mat, int t) {
int m = mat.length, n = mat[0].length;

// 第一次二分:定位到所在行(从上往下,找到最后一个满足 mat[x]][0] <= t 的行号)
int l = 0, r = m - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (mat[mid][0] <= t) {
l = mid;
} else {
r = mid - 1;
}
}

int row = r;
if (mat[row][0] == t) return true;
if (mat[row][0] > t) return false;

// 第二次二分:从所在行中定位到列(从左到右,找到最后一个满足 mat[row][x] <= t 的列号)
l = 0; r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (mat[row][mid] <= t) {
l = mid;
} else {
r = mid - 1;
}
}
int col = r;

return mat[row][col] == t;
}
}

  • 时间复杂度:$O(\log{m} + \log{n})$
  • 空间复杂度:$O(1)$

二分解法(二)

当然,因为将二维矩阵的行尾和行首连接,也具有单调性。

我们可以将「二维矩阵」当做「一维矩阵」来做。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public boolean searchMatrix(int[][] mat, int t) {
int m = mat.length, n = mat[0].length;
int l = 0, r = m * n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (mat[mid / n][mid % n] <= t) {
l = mid;
} else {
r = mid - 1;
}
}
return mat[r / n][r % n] == t;
}
}

  • 时间复杂度:$O(\log{(m * n)})$
  • 空间复杂度:$O(1)$

抽象 BST 解法

我们可以将二维矩阵抽象成「以右上角为根的 BST」:

image.png

那么我们可以从根(右上角)开始搜索,如果当前的节点不等于目标值,可以按照树的搜索顺序进行:

  1. 当前节点「大于」目标值,搜索当前节点的「左子树」,也就是当前矩阵位置的「左方格子」,即 y—
  2. 当前节点「小于」目标值,搜索当前节点的「右子树」,也就是当前矩阵位置的「下方格子」,即 x++

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
int m, n;
public boolean searchMatrix(int[][] mat, int t) {
m = mat.length; n = mat[0].length;
int x = 0, y = n - 1;
while (check(x, y) && mat[x][y] != t) {
if (mat[x][y] > t) {
y--;
} else {
x++;
}
}
return check(x, y) && mat[x][y] == t;
}
boolean check(int x, int y) {
return x >= 0 && x < m && y >= 0 && y < n;
}
}

  • 时间复杂度:$O(m+n)$
  • 空间复杂度:$O(1)$

拓展

如果你掌握了上述解法的话,你还可以试试这题:

240. 搜索二维矩阵 II


最后

这是我们「刷穿 LeetCode」系列文章的第 No.74 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!