Elegant C++ solution using STL, 3 lines, 12ms.


  • 1
    M

    At first, use "lower_bound" to find a row(matrix[i]) in matrix that:

    matrix[i-1].back() < target <= matrix[i].back()
    

    Then, use "binary_search" to search "target" in this row(matrix[i]).

    The AC code demonstrates the power and elegance of STL:

    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            auto compfunc = [](const vector<int> &v, const int x) {return v.back() < x;};
            auto itr = lower_bound(matrix.begin(), matrix.end(), target, compfunc);
            return itr != matrix.end() && binary_search(itr->begin(), itr->end(), target);
        }
    };
    

    You can get more information about "lower_bound" and "binary_search" at:

    http://www.cplusplus.com/reference/algorithm/lower_bound/
    http://www.cplusplus.com/reference/algorithm/binary_search/


Log in to reply
 

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