Leetcode 74: 2 차원 행렬 검색 (가장 자세 한 해법!!)

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

문제 풀이 의 사고 방향.
이 문 제 는 매우 간단 하 다. 먼저 생각 하 는 가장 간단 한 사 고 는 바로 왼쪽 에서 오른쪽으로 위 에서 아래로 행렬 을 옮 겨 다 니 는 것 이다.

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix:
            return False
        r, c = len(matrix), len(matrix[0])
        for i in range(r):
            for j in range(c):
                if matrix[i][j] == target:
                    return True
            
        return False

그러나 이것 은 분명히 가장 좋 은 방법 이 아니다. 문 제 를 찾 는 데 있어 서 우 리 는 사실 모두 2 분 의 검색 을 통 해 해결 할 수 있 는 지 생각해 볼 수 있다.

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix:
            return False
        r, c = len(matrix), len(matrix[0])
        left, right = 0, r*c

        while left < right:
            mid = (left+right)//2
            m, n = mid//c, mid%c
            if matrix[m][n] == target:
                return True
            elif matrix[m][n] < target:
                left = mid + 1
            else:
                right = mid
            
        return False

이 문 제 는 우리 가 python 의 bisect 가방 을 사용 하면 매우 pythonic 코드 를 쓸 수 있다.

import bisect
class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        i = bisect.bisect(matrix, [target])
        if i < len(matrix) and matrix[i][0] == target:
            return True
        row = matrix[i-1]
        j = bisect.bisect_left(row, target)
        return j < len(row) and row[j] == target

reference:
https://leetcode.com/problems/search-a-2d-matrix/discuss/26248/6-12-lines-O(log(m)-+-log(n))-myself+library
나 는 이 문제 의 다른 언어 버 전 을 GitHub Leetcode 에 추가 했다.
문제 가 있 으 면 지적 해 주세요!!