240. Search a 2D Matrix II

起初我想說找到對的行跟列, 然後做binary search

時間複雜度是O(max(mlogn, nlogm))

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        vector<int> start_i;
        vector<int> start_j;
        int m = matrix.size();
        int n = matrix[0].size();
        for(int row = 0; row < m; row++){
            if(matrix[row][0] <= target){
                start_i.push_back(row);
            }
        }
        for(int col = 0; col < n; col++){
            if(matrix[0][col] <= target){
                start_j.push_back(col);
            }
        }
        for(auto col: start_j){
            int l = 0;
            int r = m - 1;
            while(l <= r){
                int mid = (r + l) /2;
                if(matrix[mid][col] == target){
                    return true;
                }else if (matrix[mid][col] < target){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
        }
        for(auto row: start_i){
            int l = 0;
            int r = n - 1;
            while(l <= r){
                int mid = (r + l) /2;
                if(matrix[row][mid] == target){
                    return true;
                }else if (matrix[row][mid] < target){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
        }
        return false;
    }
};

但發現時間太慢了有O(m+n)的

有個觀察點, 右上角的點往左一定變小, 往下一定變大, 所以我們就是當> target就往左,< target就往下, 這沒有神仙指點還真的不會特別去注意呢

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int r = 0;
        int c = n - 1;
        while(r < m && c >=0){
            if(matrix[r][c] == target){
                return true;
            }
            if(matrix[r][c] > target){
                c--;
            }else{
                r++;
            }
        }
        return false;
    }
};