So clear solve for c++


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

  • 0
    M

    Brilliant solution.


  • 0
    M

    i like this solution


  • 7
    Z

    referring your solution, i revised it into iteration. And it become more clear.The essence of solution is to use a search path starting from top right corner.using recursion may lead to hide essence of solution and more difficult to calculate it's time complexity.

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    
        int row = 0;
        int col = matrix[0].size() - 1;
        
        while(row < matrix.size() && col >= 0) {
            
            if(matrix[row][col] == target) return true;
            if(matrix[row][col] < target) { row++; continue; }
            if(matrix[row][col] > target) { col--; continue; }
            
        }
        
        return false;
        
    }

  • 0
    R

    so the time complexity should be m + n, right?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.