O(logm+logn) solution (AC) using C++


  • -1
    F

    class Solution {
    public:
    bool search(vector<vector<int>> &matrix,int si,int ei,int sj,int ej,int target){

        if(si>ei||sj>ej
           ||matrix[si][sj]>target
           ||matrix[ei][ej]<target) 
           return false;
        //si is up side,ei is down side,sj is left side, ej is right side 
        int mi=(si+ei)/2;
        int mj=(sj+ej)/2;
        
        if(matrix[mi][mj]==target)
            return true;
        else if(matrix[mi][mj]<target){
            return search(matrix,si,mi,mj+1,ej,target)
                   ||search(matrix,mi+1,ei,sj,mj,target)
                   ||search(matrix,mi+1,ei,mj+1,ej,target);
        }else{
            return search(matrix,si,mi-1,mj,ej,target)
                   ||search(matrix,mi,ei,sj,mj-1,target)
                   ||search(matrix,si,mi-1,sj,mj-1,target);
        }
    }
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()) return false;
        
        return search(matrix,0,matrix.size()-1,0,matrix[0].size()-1,target);
    }
    

    };


  • 0

    That's not O(logm+logn) (or not correct).


  • 0
    F

    you are right, it's a quite heavy algorithm indeed. But it works indeed.


Log in to reply
 

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