LeetCode240 搜索二维矩阵

发表于 | 分类于 |
字数统计: 259 | 阅读时长 ≈ 1

链接： https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

题面

给定一个二维矩阵，已知每行和每列都是增序的，尝试设计一个快速搜索一个数字是否在矩阵中存在的算法。

解法

想法是用两个指针表示当前的坐标，然后根据当前值比target大或是小进行移动
结果发现没法移动，因为向下移也是变大，向右移也是变大就卡住了
正解确实也是这样做的，只是选定的起点有说法
可以从左下或是右上开始进行搜索，这样两个方向就会是不一样的趋势
是一个好的剪枝 必然可以找到结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int i = 0, j = n - 1;
        while(i < m && j >= 0) {
            if (matrix[i][j] > target) {
                j--;
            }
            else if (matrix[i][j] < target) {
                i++;
            }
            else {
                return true;
            }
        }
        return false;
    }
};