【LeetCode】74. Search a 2D Matrix 解答・解説【Python】

問題
1. 原文
2. 内容
解答
1. 解答1：Pytnon,　二分探索
2. 解答2:Python,　二分探索
メモ・参考・感想

問題

原文

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

1
2

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

1
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

-10⁴ <= matrix[i][j], target <= 10⁴

内容

以下の2つの性質を持つm×nの整数行列が与えられます。

・各行は非降順(つまり昇順)に並べられている

・各行の最初の値は、前の行の最後の値よりも大きい

整数targetが与えられるので、targetが行列内にあればTrue、なければFalseを返してください。

解答は時間計算量O(log(m*n))でなければなりません。

※正しくない可能性があります。

解答

解答1：Pytnon,　二分探索

class Solution:
    #matrixの各要素をforループで走査し、targetの有無をbinary_search関数で調べる
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for element in matrix:
            if self.binary_search(element, target) is True:
                return True
        return False

    #与えられた配列からtargetを探す。
    def binary_search(self, element, target) -> bool:
        left = 0
        right = len(element) - 1
        while left <= right:
            middle = (left + right) // 2
            if target == element[middle]: return True
            elif target < element[middle]: right = middle - 1
            elif target > element[middle]: left = middle + 1
        return False

class Solution:

#matrixの各要素をforループで走査し、targetの有無をbinary_search関数で調べる

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

for element in matrix:

if self.binary_search(element, target) is True:

return True

return False

#与えられた配列からtargetを探す。

def binary_search(self, element, target) -> bool:

left = 0

right = len(element) - 1

while left <= right:

middle = (left + right) // 2

if target == element[middle]: return True

elif target < element[middle]: right = middle - 1

elif target > element[middle]: left = middle + 1

return False

これは時間計算量がO(nlog(m))な気がする。

問題はO(log(mn))なので、条件を満たしていない。

追記

2番目の性質と二分探索でさらに探索範囲を絞ることができるかもしれない。

解答2:Python,　二分探索

class Solution:
    #matrixの各要素をforループで走査し、targetの有無をbinary_search関数で調べる
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        #探索範囲を絞り込む
        heads_of_matrix = [matrix[i][0] for i in range(len(matrix))]
        tmp_list = self.helper(heads_of_matrix, target)
        
        if tmp_list[0] == 1:
            return True
        else:
            target_row = tmp_list[1]
            answer = self.binary_search(matrix[target_row], target)
            if answer is True:
                return True
            else:
                return False

    #与えられた配列からtargetを探す。
    def binary_search(self, element, target) -> bool:
        left = 0
        right = len(element) - 1
        while left <= right:
            middle = (left + right) // 2
            if target == element[middle]: return True
            elif target < element[middle]: right = middle - 1
            elif target > element[middle]: left = middle + 1
        return False

    #matrixの行頭の値の集合とtargetを二分探索で比較して探索範囲を絞り込む
    def helper(self, heads_of_matrix, target):
        left = 0
        right = len(heads_of_matrix) - 1
        while left <= right:
            middle = (left + right) // 2
            if target == heads_of_matrix[middle]: return [1, middle]
            elif target < heads_of_matrix[middle]: right = middle - 1
            elif target > heads_of_matrix[middle]: left = middle + 1
        if target < heads_of_matrix[middle]: return [0, middle-1]
        if target > heads_of_matrix[middle]: return [0, middle]

class Solution:

#matrixの各要素をforループで走査し、targetの有無をbinary_search関数で調べる

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

#探索範囲を絞り込む

heads_of_matrix = [matrix[i][0] for i in range(len(matrix))]

tmp_list = self.helper(heads_of_matrix, target)

if tmp_list[0] == 1:

return True

else:

target_row = tmp_list[1]

answer = self.binary_search(matrix[target_row], target)

if answer is True:

return True

else:

return False

#与えられた配列からtargetを探す。

def binary_search(self, element, target) -> bool:

left = 0

right = len(element) - 1

while left <= right:

middle = (left + right) // 2

if target == element[middle]: return True

elif target < element[middle]: right = middle - 1

elif target > element[middle]: left = middle + 1

return False

#matrixの行頭の値の集合とtargetを二分探索で比較して探索範囲を絞り込む

def helper(self, heads_of_matrix, target):

left = 0

right = len(heads_of_matrix) - 1

while left <= right:

middle = (left + right) // 2

if target == heads_of_matrix[middle]: return [1, middle]

elif target < heads_of_matrix[middle]: right = middle - 1

elif target > heads_of_matrix[middle]: left = middle + 1

if target < heads_of_matrix[middle]: return [0, middle-1]

if target > heads_of_matrix[middle]: return [0, middle]

行頭の値とtargetを二分探索を使いつつ比較することで、どの行で二分探索を行うかを絞り込みたくて書いていた解答。

でも、各行の最初の値をリストにするためにfor文を使っているので、時間計算量は解答1から改善していないと思う。

submissionをしてみても、時間計算量は44msから変化がない上に、空間計算量が増えているので、使用するメモリが増えた分改悪されている。

メモ・参考・感想

前：46. Permutations

次：153. Find Minimum in Rotated Sorted Array

LeetCode 解答・解説記事一覧

問題

原文

内容

解答

解答1：Pytnon, 二分探索

解答2:Python, 二分探索

メモ・参考・感想

コメント

解答1：Pytnon,　二分探索

解答2:Python,　二分探索