0240. 搜索二维矩阵 II

[giscus[bot]]

0240. 搜索二维矩阵 II

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)$。