Share my O(m+n) solution


  • 5
    N

    I search from right up corner:row=0,col=m-1

    1. if matrix[row][col] is equal target,return true.
    2. if matrix[row][col] is less than target, row++; indicate that this row can't contain target.because this one in this line is the biggest one,counting from 'row'.
    3. if matrix[row][col] is greater than target,col--; indicate that this column can't contain target.because this one in this column is the smallest one,counting from 'col'.

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

  • 2
    A

    It's O(m + n), not O(max(m, n)). The worst situation will be at the last row and the first column.

    There is a solution has O(logm + logn)


  • 0
    N

    thanks,u are right


Log in to reply
 

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