有序二维矩阵搜索问题

问题

在一个大小为 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;

    while (row < rows && col >= 0) {
        int vertex = matrix[row][col];

        if (target < vertex) {
            col--;
        } else if (target > vertex) {
            row++;
        } else {
            return true;
        }
    }
    return false;
}

复杂度分析

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

相似问题

leetcode 上有一个类似的问题 - 1351. 统计有序矩阵中的负数

给你一个 m * n 的矩阵 grid,矩阵中的元素无论是按行还是按列,都以非递增顺序排列。 请你统计并返回 grid 中 负数 的数目。

采用类似的思路,可以从右上角顶点出发,此时右上角始终有这样的性质: 当前行最小值、当前列最大值。

有序矩阵中统计负数的数目 C++
class Solution {
   public:
    int countNegatives(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int i = 0;
        int j = n - 1;
        int count = 0;
        // 右上角性质: 当前行最小值、当前列最大值
        while (i < m && j >= 0) {
            if (grid[i][j] < 0) {
                // 当前列此行以下的部分肯定全部 < 0
                count += m - i;
                // 排除当前列
                j--;
            } else {
                // 当前行左边的部分肯定都 >= 0
                // 排除当前行
                i++;
            }
        }
        return count;
    }
};

结语

不过,需要指出,本方法虽然简洁优美,但是,在矩阵比较大的情况下,它不是时间复杂度最优的方法。 参考 再探有序二维矩阵搜索问题之分治解法

(完)

本文原始链接地址: https://writings.sh/post/algorithm-search-sorted-2d-matrix

王超 ·
喜欢这篇文章吗?
微信扫码赞赏
评论 首页 | 归档 | 算法 | 订阅