2 차원 매트릭스 검색 II (LeetCode 240 번) 자바 구현

제목 설명
효율 적 인 알고리즘 을 만들어 서 검색 하 다. m x n 매트릭스 매트릭스 의 목표 값 target 입 니 다.이 행렬 은 다음 과 같은 특성 을 가지 고 있다.
각 줄 의 요 소 는 왼쪽 에서 오른쪽으로 오름차 순 으로 배열 되 어 있다.각 열의 요 소 는 위 에서 아래로 오름차 순 으로 배열 된다.예시:
현재 매트릭스 매트릭스 행렬 은 다음 과 같 습 니 다.
[   [1,   4,  7, 11, 15],   [2,   5,  8, 12, 19],   [3,   6,  9, 16, 22],   [10, 13, 14, 17, 24],   [18, 21, 23, 26, 30] 주어진 대상 = 5, 귀환 true。
정 하 다 target = 돌아오다 false。
2. 문제 풀이 사고
방법 1: 왼쪽 아래 의 수 matrix [x] [y] 부터 비교 합 니 다. target > matrix [x] [y] 때 는 맨 왼쪽 첫 번 째 열 을 버린다.하면, 만약, 만약... 
방법 2: 이분법 을 사용 하여 맨 오른쪽 열 부터 먼저 2 분 에 target 을 찾 아 몇 번 째 줄 을 찾 습 니 다.다시 이분법 으로 이 줄 의 몇 번 째 수 를 찾 아 라.target 의 존재 여 부 를 판단 합 니 다.시간 복잡 도 는 O (logn + logm) 이 고 공간 복잡 도 는 O (1) 이다.
3. 자바 코드 실행 가능
방법 1:

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

방법 2:

class Solution {
    private boolean find(int[] matrixRow, int target) {
        int left = 0, right = matrixRow.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (matrixRow[mid] == target) {
                return true;
            } else if (matrixRow[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return matrixRow[left] == target;
    }
    
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        if (rows == 0) return false;
        int cols = matrix[0].length;
        if (cols == 0) return false;
        
        int topRow = 0, bottomRow = rows - 1;
        while (topRow < bottomRow) {
            int mid = (topRow + bottomRow) / 2;
            if (matrix[mid][cols - 1] < target) {
                topRow = mid + 1;
            } else {
                bottomRow = mid;
            }
        }
        
        int rowToScan = topRow;
        boolean found = false;
        while (rowToScan < rows && matrix[rowToScan][0] <= target) {
            if (find(matrix[rowToScan], target)) {
                return true;
            } else {
                ++ rowToScan;
            }
        }
        
        return false;
    }
}