1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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(), columns = matrix[0].size();
        // 从右上角(0, columns)->(rows, 0)
        // 如果小于就target就下移，大于左移
        int x = 0, y = columns - 1;
        while (x < rows && y >= 0) {
            if (matrix[x][y] < target) {
                x ++;
            } else if (matrix[x][y] > target) {
                y --;
            } else {
                return true;
            }
        }
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    bool dfs(vector<vector<int>>& matrix, int target, int x, int y) {
        if (x >= matrix.size() || y >= matrix[0].size())  {
            return false;
        }
        
        if (matrix[x][y] == target) {
            return true;
        } else if (matrix[x][y] < target) {
            return dfs(matrix, target, x + 1, y) || dfs(matrix, target, x, y +1);
        } else {
            return false;
        }
    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        return dfs(matrix, target, 0, 0);
    }
};