Vue.js

Appearance

On this page

实战：搜索二维矩阵 II ​

LeetCode 240. 搜索二维矩阵 II | 难度：中等

与上一题不同，这个矩阵行与行之间没有严格的大小关系。

题目描述 ​

编写一个高效的算法来搜索 m x 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，向左移动（排除当前列）
  • 如果当前值 < target，向下移动（排除当前行）
  • 如果相等，找到

代码实现 ​

typescript
function searchMatrix(matrix: number[][], target: number): boolean {
  const m = matrix.length;
  const n = matrix[0].length;
  
  // 从右上角开始
  let row = 0;
  let col = n - 1;
  
  while (row < m && col >= 0) {
    const val = matrix[row][col];
    
    if (val === target) {
      return true;
    } else if (val > target) {
      col--;  // 当前值太大，向左
    } else {
      row++;  // 当前值太小，向下
    }
  }
  
  return false;
}

为什么选右上角？ ​

右上角：matrix[0][n-1]
- 向左：值减小
- 向下：值增大

可以根据比较结果确定唯一方向

而左上角（值最小）和右下角（值最大）无法确定方向。

图示 ​

target = 5

   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

15 > 5, col--
11 > 5, col--
7 > 5, col--
4 < 5, row++
5 === 5, 返回 true

复杂度分析 ​

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

与搜索二维矩阵 I 的对比 ​

题目矩阵特点算法时间复杂度
版本 I完全有序二分O(log(mn))
版本 II行列有序右上角搜索O(m+n)

在 GitHub 上编辑此页