240. Search a 2D Matrix II

Posted on | Edited on | Views:

LeetCode

Approach 1: Binary Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    private boolean binarySearch(int[][] matrix,int target,int start,boolean isVertical){
        int l=start;
        int r=isVertical?matrix.length-1:matrix[0].length-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(isVertical){
                if(matrix[mid][start]==target) return true;
                else if(matrix[mid][start]>target) r=mid-1;
                else l=mid+1;
            }else{
                if(matrix[start][mid]==target) return true;
                else if(matrix[start][mid]>target) r=mid-1;
                else l=mid+1;
            }
        }
        return false;
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null||matrix.length==0) return false;
        int shorterDim=Math.min(matrix.length,matrix[0].length);
        for(int i=0;i<shorterDim;i++){
            boolean verticalFound=binarySearch(matrix,target,i,true);
            boolean horizontalFound=binarySearch(matrix,target,i,false);
            if(verticalFound||horizontalFound) return true;
        }
        return false;
    }
}

Approach 2: Divide and Conquer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private boolean dividConque(int left,int up,int right,int down,int[][] matrix,int target){
        if(left>right||up>down) return false;
        else if(target<matrix[up][left]||target>matrix[down][right]) return false;
        
        int mid=left+(right-left)/2;
        int row=up;
        while(row<=down&&matrix[row][mid]<=target){
            if(matrix[row][mid]==target) return true;
            row++;
        }
        
        return dividConque(left,row,mid-1,down,matrix,target)|| // left down area
            dividConque(mid+1,up,right,row-1,matrix,target); // right up area
        
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null||matrix.length==0) return false;
        return dividConque(0,0,matrix[0].length-1,matrix.length-1,matrix,target);
    }
}

Approach 3: Search Space Reduction

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // start our "pointer" in the bottom-left
        int row = matrix.length-1;
        int col = 0;

        while (row >= 0 && col < matrix[0].length) {
            if (matrix[row][col] > target) {
                row--;
            } else if (matrix[row][col] < target) {
                col++;
            } else { // found it
                return true;
            }
        }

        return false;
    }
}

0%