[Leetcode] 74. Search a 2D Matrix

Problem:

You are given an m x n integer matrix matrix with the following two properties:

Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

 

Example 1:


Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:


Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
 

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

 

Solution1:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        concat_mat = []
        for mat in matrix:
            concat_mat += mat 
        left,right = 0 , len(concat_mat) - 1 
        mid = 0 
        while left <= right:
            mid = (left + right) // 2 
            if concat_mat[mid] == target:
                return True 
            elif concat_mat[mid] < target:
                left = mid + 1 
            else:
                right = mid - 1 
        return False

위 문제는 List들을 concat 한 다음 Binary Search를 수행하였다. 

 

내가 참조한 Solution2:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False 
        m,n = len(matrix),len(matrix[0])
        left,right = 0, m*n - 1 

        while left <= right:
            mid = (left+right) // 2 
            mid_row,mid_col = divmod(mid,n)
            if target == matrix[mid_row][mid_col]:
                return True 
            elif matrix[mid_row][mid_col] < target:
                left = mid + 1 
            else:
                right = mid - 1 
        return False

이 Solution은 2D 를 하나의 1D로 봐도 된다는 생각으로 코드를 작성한 것 같다. 이 코드에서 눈여겨볼 곳은 divmod다. divmode는 mid를 n으로 나눈 몫과 나머지를 반환해 준다. 예를 들면 , divmod(14,5)가 있으면 ---> return (2,4)를 반환해 준다. 따라서, 2D를 1D처럼 이동할 수 있게 해 준다.