LeetCode 240 [Search a 2D Matrix II]

1338 단어
원제
효율 적 인 알고리즘 을 써 서 m 를 검색 하 다.×행렬 의 값, 이 값 이 나타 날 지 여 부 를 되 돌려 줍 니 다.이 행렬 은 다음 과 같은 특성 을 가지 고 있다. 각 줄 의 정 수 는 왼쪽 에서 오른쪽으로 정렬 된다.각 열의 정 수 는 위 에서 아래로 정렬 되 어 있다.줄 이나 열 마다 중복 되 는 정수 가 없습니다.
다음 행렬 을 고려 합 니 다:
[
    [1, 3, 5, 7],
    [2, 4, 7, 8],
    [3, 5, 9, 10]
]

target = 3 을 드 리 고 True 로 돌아 갑 니 다.
문제 풀이 의 사고 방향.
  • 시간 복잡 도 를 생각 할 때 몇 가지 답 이 있 는 지 를 고려 할 수 있다. 예 를 들 어 permutation 시간 복잡 도 는 n2
  • 가 아니 라 2n 일 것 이다.
  • [Search a 2D Matrix I] 는 각 줄 의 마지막 줄 이 다음 줄 의 첫 번 째 줄 보다 작 기 때문에 전체 2 차원 배열 을 증가 하 는 1 차원 배열 로 볼 수 있 고 본 문 제 는 다르다.
  • 시작 점 을 왼쪽 하단 으로 설정 합 니 다. 예 를 들 어 본 문제, target > 3 이면 첫 번 째 열 은 건 너 뛰 고 target < 3 이면 마지막 줄 은 건 너 뛰 기
  • 전체 코드
    class Solution(object):
        def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            if not matrix:
                return 0
                
            depth = len(matrix)
            width = len(matrix[0])
            row, col = depth - 1, 0
            while row >= 0 and col < width:
                if matrix[row][col] == target:
                    return True
                elif matrix[row][col] > target:
                    row -= 1
                else:
                    col += 1
            return False
    

    좋은 웹페이지 즐겨찾기