My c++ solution 12ms


  • 0
    W
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            //先对最后一列二分查找,找到等于目标就返回true或者大于目标的最小值,再对那一行进行二分查找
        int m=matrix.size();
        if(m==0)
        return false;
        int n=matrix[0].size();
        int low=0;
        int high=m-1;
        while(low<high)
        {
            int mid=(low+high)/2;
            if(matrix[mid][n-1]==target)
            return true;
            if(matrix[mid][n-1]>target)
            high=mid;
            else
            low=mid+1;
        }
            int row = high;
            low=0;
            high=n-1;
            while(low<=high)
            {
                int mid=(low+high)/2;
                if(matrix[row][mid]==target)
                return true;
                if(matrix[row][mid]>target)
                high=mid-1;
                else
                low=mid+1;
            }
            return false;
        }
    };

Log in to reply
 

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