240. Search a 2D Matrix II.md

240. Search a 2D Matrix II

Thinking:

• Method 1:TLE
  • 通过递归不断向右或是向下。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0) return false;
        int height = matrix.length;
        int width = matrix[0].length;
        return find(matrix, target, 0, 0, height, width);
    }
    private static boolean find(int[][] matrix, int target, int row, int col, int height, int width){
        if(row >= height || col >= width) return false;
        else if(matrix[row][col] > target) return false;
        else if(matrix[row][col] == target) return true;
        else{
            return find(matrix, target, row + 1, col, height, width) || find(matrix, target, row, col + 1, height, width);
        }
    }
}

• Method 2: 通过二分法查找每一行。AC

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0) return false;
        int height = matrix.length;
        int width = matrix[0].length;
        for(int i = 0; i < height; i++){
            int col = binarySearchRow(matrix[i], target, 0, width - 1);
            if(col != -1) return true;
        }
        return false;
    }
    private static int binarySearchRow(int[] arr, int target, int low, int high){
        if(low > high) return -1;
        int mid = (low + high) / 2;
        if(arr[mid] == target) return mid;
        else if(arr[mid] > target)
            return binarySearchRow(arr, target, low, mid - 1);
        else
            return binarySearchRow(arr, target, mid + 1, high);
    }
}

• Method 3:从右上角开始查找，小了下移，大了左移

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0) return false;
        int height = matrix.length;
        int width = matrix[0].length;
        int row = 0; int col = width - 1;
        while(row < height && col >= 0){
            if(target == matrix[row][col]) return true;
            else if(target > matrix[row][col]) row++;
            else col--;
        }
        return false;
    }
}

Second Time

1. I solve this question in the same way as Method 3 in the first time.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0) return false;
        int height = matrix.length, width = matrix[0].length;
        int curRow = 0, curCol = width - 1;
        while(curRow >= 0 && curRow < height && curCol >= 0 && curCol < width){
            int cur = matrix[curRow][curCol];
            if(target == cur){
                return true;
            }else if(cur > target){
                curCol--;
            }else{
                curRow++;
            }
        }
        return false;
    }
}