Share my C++ solution,time complexity is O(log m + log n)


  • 1
    V
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int row = matrix.size();
            if (row == 0)
                return false;
            int col = matrix[0].size();
            if (col == 0)
                return false;
                
            if (target < matrix[0][0] || target > matrix[row-1][col-1])
                return false;
                
            int left = 0, right = row * col - 1, mid = 0, value = 0;
            
            while (left <= right)
            {
                mid = left + (right - left) / 2;
                value = matrix[mid / col][mid % col];
                
                if (target == value)
                    return true;
                else if (target < value)
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            
            return false;
        }
    };
    

    or:

    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int row = matrix.size();
            if (row == 0)
                return false;
            int col = matrix[0].size();
            if (col == 0)
                return false;
                
            if (target < matrix[0][0] || target > matrix[row-1][col-1])
                return false;
                
            int l1 = 0, r1 = row - 1, mid1 = 0;
            int l2 = 0, r2 = col - 1, mid2 = 0;
            
            while (l1 <= r1)
            {
                mid1 = l1 + (r1 - l1) / 2;
                if (target == matrix[mid1][0] || target == matrix[mid1][col-1])
                    return true;
                if (target > matrix[mid1][0] && target < matrix[mid1][col-1])
                {
                    l2 = 0, r2 = col - 1;
                    
                    while (l2 <= r2)
                    {
                        mid2 = l2 + (r2 - l2) / 2;
                        if (target == matrix[mid1][mid2])
                            return true;
                        else if (target < matrix[mid1][mid2])
                            r2 = mid2 - 1;
                        else
                            l2 = mid2 + 1;
                    }
                    
                    return false;
                }
                
                if (target < matrix[mid1][0])
                    r1 = mid1 - 1;
                else if (target > matrix[mid1][col-1])
                    l1 = mid1 + 1;
            }
            
            return false;
        }
    };

Log in to reply
 

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