20 lines C++ code using STL algorithm


  • 0
    A
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if(matrix.empty())
                return false;
            vector<int> firstCol;
            for(auto v : matrix)
            firstCol.push_back(v[0]);
            if(binary_search(firstCol.begin(), firstCol.end(), target))
                return true;   //否则不知道low行是否需要搜索,因为搜索low行会有越界的危险
            vector<int>::iterator iter = lower_bound(firstCol.begin(), firstCol.end(), target);
            int low = iter - firstCol.begin();
            for(int i = 0; i < low; i++)//前面已判断,不必搜索low行
            {
                if(binary_search(matrix[i].begin(), matrix[i].end(), target))
                    return true;
            }
            return false;
        }
    };

Log in to reply
 

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