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

输入：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 = 20
输出：false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答 & 代码

从矩阵左下角开始搜索：

• 如果当前元素等于目标值，返回 true
• 如果当前元素大于目标值，则上移一行，继续搜索
• 如股票当前元素小于目标值，则右移一列，继续搜索

时间复杂度 O(rows+cols)，空间复杂度 O(1)

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return false;

        int rows = matrix.size();
        int cols = matrix[0].size();

        // 从左下角开始搜索
        int row = rows - 1;
        int col = 0;
        while(row >= 0 && col < cols)
        {
            if(matrix[row][col] == target)
                return true;
            else if(matrix[row][col] > target)
                --row;
            else
                ++col;
        }
        return false;
    }
};

执行结果：

执行结果：通过

执行用时：104 ms, 在所有 C++ 提交中击败了 79.17% 的用户
内存消耗：14.6 MB, 在所有 C++ 提交中击败了 6.44% 的用户