2-clean-C++ implementation with detailed complexity analysis


  • 10

    Here is the O(M+N) solution, It is important to make it clear we choose the position

         right-up-corner-position : can help us to exclude a column or a row
    

    So by judging the right-up-corner-value, we can exclude a column or a row one loop, so the loop is
    O(M+N) time complexity.

    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int m=matrix.size();
            if(m==0)  return false;
            int n=matrix[0].size();
            /*** start from the right-up-position ***/
            int i=0, j=n-1;
            while(i<m && j>=0){
                if(matrix[i][j]==target)  return true;
                /*** the element-of-column-j >= matrix[i][j] > target ***/
                else if(matrix[i][j]>target)  j--;
                /*** the element-of-row-i <= matrix[i][j] < target ***/
                else   i++;
            }
            return false;
        }
    };
    

    Here is a recursion-version-implementation, by analyzing the time complexity

      T(N)=3*(T(N/4)) + O(1)
    

    Based the master theory,

     f(n) = O(1) = O(log(4, 3-e))    with e=2   
    

    So

     T(n) = O(N ^ log(4, 3) )    <  O(N)
    

    here is the C++ implementation:

       class Solution {
        public:
            bool searchMatrix(vector<vector<int>>& matrix, int target) {
                if(matrix.size()==0) return false;
                int row=matrix.size(), col=matrix[0].size();
                return help(matrix, 0, row-1, 0, col-1, target);
            }
            
            bool help(vector<vector<int>>& matrix, int row_start, int row_end, int col_start, int col_end, int target) {
                if(row_start>row_end || col_start>col_end)  return false;
                int row_mid=(row_start+row_end)/2, col_mid=(col_start+col_end)/2;
                if(matrix[row_mid][col_mid]==target)    return true;
                else if(matrix[row_mid][col_mid]>target){
                    /*** left-up || left-down || right-up ***/
                    return help(matrix, row_start, row_mid-1, col_start, col_mid-1, target) ||
                        help(matrix, row_mid, row_end, col_start, col_mid-1, target) ||
                        help(matrix, row_start, row_mid-1, col_mid, col_end, target);
                }
                else{
                    /*** right-down || left-down || right-up ***/
                    return help(matrix, row_mid+1, row_end, col_mid+1, col_end, target) ||
                        help(matrix, row_mid+1, row_end, col_start, col_mid, target) ||
                        help(matrix, row_start, row_mid, col_mid+1, col_end, target);
                }
            }
        };

  • 0

    Here is a recursion-version-implementation, by analyzing the time complexity

    T(N)=3*(T(N/4)) + O(1)
    

    here is the C++ ...

    Looks like you forgot the analysis.


  • 0

    I have added the complexity analysis @StefanPochmann


  • 0

    Rather bad. What is N?


Log in to reply
 

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