LeetCode 240 Search a 2D Matrix II

Posted on | In | 阅读

可以从右上角或者左下角开始。以右上角为例，若这个数比target大，那么这一列都不可能，若比target小，那么这一行都不可能。这样逐渐收缩都target的位置。如果到最后都没找到target，返回false

C++ Code

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