240. 搜索二维矩阵 II

下自成蹊 / 2023-09-04 / 原文

编写一个高效的算法来搜索 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

> 思路
我们可以发现矩阵具有如下性质:

因此我们可以从整个矩阵的右上角开始枚举，假设当前枚举的数是 x：

如果 x 等于target，则说明我们找到了目标值，返回true；
如果 x小于target，则 x左边的数一定都小于target，我们可以直接排除当前一整行的数；
如果 x 大于target，则 x 下边的数一定都大于target，我们可以直接排除当前一整列的数；
排除一整行就是让枚举的点的横坐标加一，排除一整列就是让纵坐标减一。当我们排除完整个矩阵后仍没有找到目标值时，就说明目标值不存在，返回false。

> 代码


class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = 0;
        int n = matrix[0].size() - 1;
        while(m < matrix.size() && n >= 0){
            if(matrix[m][n] == target){
                return true;
            }
            else if(matrix[m][n] < target){
                m++;
            }
            else{
                n--;
            }
        }
        return false;       
    }
};