C++ two methods


  • 0
    X
    class Solution {
    public:
        // ooh, such a slow solution, 1892ms
        bool find(int x1, int y1, int x2, int y2, vector<vector<int>>& matrix, int target){
            if(x1 > x2 || y1 > y2){
                return false;
            }
            int midx = x1 + (x2 - x1) / 2;
            int midy = y1 + (y2 - y1) / 2;
            if(matrix[midx][midy] == target){
                return true;
            }else if(matrix[midx][midy] < target){
                return find(x1, midy + 1, midx, y2, matrix, target) ||
                       find(midx + 1, midy + 1, x2, y2, matrix, target) ||
                       find(midx + 1, y1, x2, midy, matrix, target);
            }else{
                return find(x1, y1, midx - 1, midy - 1, matrix, target)||
                       find(midx, y1, x2, midy - 1, matrix, target) ||
                       find(x1, midy, midx - 1, y2, matrix, target);
            }
        }
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int xsize = matrix.size();
            if(xsize == 0){
                return false;
            }
            int ysize = matrix[0].size();
            return find(0, 0, xsize - 1, ysize - 1, matrix, target);
        }
        /* O(m + n) 188ms
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int xsize = matrix.size();
            if(xsize == 0){
                return false;
            }
            int ysize = matrix[0].size();
            int i = 0, j = ysize - 1;
            while(i < xsize && j >= 0){
                if(matrix[i][j] == target){
                    return true;
                }else if(matrix[i][j] < target){
                    ++i;
                }else{
                    --j;
                }
            }
            return false;
        }
        */
    

    };


Log in to reply
 

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