leetcode 74. 2 차원 행렬 을 검색 하 는 것 을 본 적 이 있 습 니까?

1056 단어 leetcode
효율 적 인 알고리즘 을 만들어 서 판단 하 다. m x n 행렬 에 목표 값 이 존재 하 는 지 여부 입 니 다.이 행렬 은 다음 과 같은 특성 을 가지 고 있다.
각 줄 의 정 수 는 왼쪽 에서 오른쪽으로 오름차 순 으로 배열 된다.각 줄 의 첫 번 째 정 수 는 이전 줄 의 마지막 정수 보다 크다.예시 1:
입력: matrix = [  [1,   3,  5,  7],   [10, 11, 16, 20],   [23, 30, 34, 50] target = 3 출력: true 예제 2:
입력: matrix = [  [1,   3,  5,  7],   [10, 11, 16, 20],   [23, 30, 34, 50] target = 13 출력: false
사고: 전체 2 차원 배열 은 질서 가 있 고 2 분 에 찾 으 면 됩 니 다.
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int start = 0;
        int end = row * col - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid / col][mid % col] == target)return true;
            else if (matrix[mid / col][mid % col] > target)end = mid - 1;
            else start = mid + 1;
        }
        return false;
    }
}

좋은 웹페이지 즐겨찾기