有序二维矩阵搜索问题

问题

在一个大小为 rows x cols 的二维矩阵中查找目标值 target , 已知此矩阵的每一行、每一列的数字都是有序的。

leetcode 题目 - 搜索二维矩阵

算法思路

问题中所说的矩阵在数学上被称为 杨氏矩阵

从右上角的视角看矩阵,考虑右上角的顶点 vertex

右上角顶点有如下性质:

  • 是第一行的最大值
  • 是最后一列的最小值

假设要找的数字是 target

  • 如果 target < vertex ,即 target 比最后一列的最小值还要小 , 即可排除最后一列。

  • 如果 target > vertex ,即 target 比第一行的最大值还要大 , 即可排除第一行。

排除完成后,继续取剩余矩阵的右上角顶点,不断应用此过程:

算法过程:

  1. 设当前矩阵的顶点为 vertex = matrix[row][col] ,初始条件下:col = cols - 1row = 0
  2. 将目标值 target 和顶点的值 vertex 进行比较:

    1. 如果 target < vertex ,则排除顶点的列,即 col--
    2. 如果 target > vertex ,则排除顶点的行,即 row++
    3. 否则,命中结果。
  3. 不断重复前两步,直到无法继续查找为止。

    row 达到 rows ,或者 col 递减为 0 的时候,结束比较,未找到。

C 语言实现

有序二维矩阵搜索问题 - C 语言实现
bool SearchSortedMatrix(int rows, int cols, int matrix[rows][cols],
                        int target) {
    if (rows <= 0 || cols <= 0) return false;

    int row = 0;
    int col = cols - 1;
    int vertex = matrix[row][col];

    while (row < rows && col >= 0) {
        if (target < vertex) {
            col--;
        } else if (target > vertex) {
            row++;
        } else {
            return true;
        }
    }
    return false;
}

复杂度分析

最差情况,找到目标值需要排除 rows 个行, cols 个列,因此时间复杂度是 O(rows + cols)

结语

不过,需要指出,本方法虽然简洁优美,但是不是时间复杂度最优的方法。 参考 Searching a Sorted Matrix Faster

(完)

* * *
评论 首页 订阅 打印 ↑顶部