0240. 搜索二维矩阵 II

[giscus[bot]]

0240. 搜索二维矩阵 II

240. 搜索二维矩阵 II 标签：二分查找、分治算法 难度：中等 题目链接 0240. 搜索二维矩阵 II - 力扣 题目大意 描述：给定一个 m×n 大小的有序整数矩阵 matrix。matrix 中的每行元素从左到右升序排列，每列元素从上到下升序排列。再给定一个目标值 target。 要求：判断矩阵中是否可以找到 target，如果可以找到 t...

https://algo.itcharge.cn/Solutions/0200-0299/search-a-2d-matrix-ii/

[Therm4l]

这里提供一种取巧的方法。
注意到每一行的最后一个数是最大的，且在同一列中上一行的数一定比下一行的数要小。
因此，我们可以从第一行的最后一列开始查找，如果目标小于这个数的话则列减小，如果大于这个数的话则行增加。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int row = 0, col = n - 1;

        while (row < m && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }
        return false;
    }
};

方法的时间复杂度为 $O(m+n)$。