スポンサーリンク

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

スポンサーリンク
スポンサーリンク
この記事は約3分で読めます。

 

問題

原文

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:

Example 2:

 

Constraints:

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

 

内容

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

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

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

 

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

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

 

 

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

 

解答

解答1:Pytnon, 二分探索

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

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

 

追記

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

 

 

解答2:Python, 二分探索

 

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

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

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

 

 

 

 

メモ・参考・感想

 

 

 

前:46. Permutations

次:153. Find Minimum in Rotated Sorted Array

LeetCode 解答・解説記事一覧

コメント