C++ 12ms 2 simple solutions


  • 0
    Z
    class Solution {
    public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //return solution1(matrix, target);   //regular search
        return solution2(matrix, target);   //binary search
    }
    private:
    bool solution1(vector<vector<int>> &matrix, int target){
        int sz = matrix.size();
        if(sz == 0) return false;
        //target too small or too large
        if(matrix[0][0] > target || matrix.back().back() < target) return false;
        for(int i = 0; i < sz; i++){
            if(matrix[i].back() >= target) return search(matrix[i], matrix[i].size(), target);
        }
    }
    bool search(vector<int> v, int sz, int t){
        if(v[0] > t) return false;
        for(int i = 0; i < sz; i++)
            if(v[i] == t) return true;
        return false;
    }
    bool solution2(vector<vector<int>> &matrix, int target){
        int sz = matrix.size();
        if(sz == 0) return false;
        //target too small or too large
        if(matrix[0][0] > target || matrix.back().back() < target) return false;
        for(int i = 0; i < sz; i++){
            if(matrix[i].back() >= target) return bSearch(matrix[i], 0, matrix[i].size() / 2, matrix[i].size(), target);
        }
    }
    bool bSearch(vector<int> &v, int lo, int mid, int hi, int t){
        if(lo > hi) return false;
        if(v[mid] > t) return bSearch(v, lo, (lo+mid-1)/2, mid - 1, t);
        if(v[mid] < t) return bSearch(v, mid + 1, (mid+1+hi)/2, hi, t);
        return true;
    }
    };

Log in to reply
 

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