[検索バイナリ]Let code 240.Search a 2D Matrix II

15113 ワード
バイナリナビゲーション 道しるべ leetcode テキストリンク
道路標識240号
左から右、上から下の順に並べられた行列でターゲット値を検索

試してみる。

class Solution:
    def searchMatrix(self, matrix, target: int) -> bool:
        m, n = len(matrix), len(matrix[0])

        first_m, first_n = 0, 0
        last_m, last_n = m - 1, n - 1

        while first_m <= last_m and first_n <= last_n:
            mid_m, mid_n = first_m + (last_m - first_m) // 2, first_n + (last_n - first_n) // 2

            if matrix[mid_m][mid_n] == target:
                return True

            elif matrix[mid_m][mid_n] > target:
                if mid_m - 1 < 0 :
                    last_m, last_n = mid_m, mid_n - 1
                elif mid_n -1 < 0 :
                    last_m, last_n = mid_m - 1, mid_n
                elif matrix[mid_m - 1][mid_n] > matrix[mid_m][mid_n - 1]:
                    last_m, last_n = mid_m - 1, mid_n
                else:
                    last_m, last_n = mid_m, mid_n - 1

            else:
                if mid_m + 1 > last_m:
                    first_m, first_n = mid_m, mid_n + 1
                elif mid_n + 1 > last_n:
                    first_m, first_n = mid_m + 1, mid_n
                elif matrix[mid_m + 1][mid_n] < matrix[mid_m][mid_n + 1]:
                    first_m, first_n = mid_m + 1, mid_n
                else:
                    first_m, first_n = mid_m, mid_n + 1

        return False
  • バイナリ検索は2次元検索
    • が可能だと思います.
  • 行列[m][n]はfirst m,first n,last m,last nに拡張され,mid−>mid m,mid n
    • をそれぞれ計算する.
  • targetが5である場合、まずlastを中間値9からより小さい上部と左側に移動し、次に9より大きい左側に移動し、
    • を継続する.
  • は陳探索と同じ原理だと思いますので、最初はそう確信して解きました.例外が出てきましたが、なぜこうなったのかよく考えてみると、当然左上隅が9より小さいに違いありませんが、黄色の部分ももっと小さい数字があるかもしれないので、すべて探索したとは思えないので、無理です...ハッハッハッハッハッハッハッハッハッハッハッ

    • 答えを出す。


    完全なプールの1つは右上または左下から始まり、col値とrow値を小さくまたは大きく調整します.
    右上から
    class Solution:
    def searchMatrix(self, matrix, target: int) -> bool:
        row, col = 0, len(matrix[0]) - 1

        while row < len(matrix) and col > -1:
            if matrix[row][col] == target :
                return True
            elif matrix[row][col] > target:
                col = col - 1
            else:
                row = row + 1

        return False

  • 図に示すように、15からtargetより小さい場合、下にtargetより大きい場合、左に移動して解き、範囲を超えた場合falseを返す.

  • これは上と異なる理由として、targetが20であれば15より大きいので、底から下を向いているときは、15から左が除外されているので、このようにすると、左と下だけを考えて、右と上が通る場所なので、すでに追及されていると考えられます.

  • 最終的にこの問題の鍵は標準がどこにあるかです...

  • バイナリナビゲーションではないので複雑度はO(m+n)である.

    説明する。


    これは、各ローにバイナリナビゲーションを適用して検索する方法にすぎません.
    class Solution:
  def searchMatrix(self, matrix, target: int) -> bool:
      rows = len(matrix)

      for row in range(rows):
          first, last = 0, len(matrix[0])-1
          while first <= last:
              mid = first + (last - first) // 2

              if matrix[row][mid] == target:
                  return True
              elif matrix[row][mid] > target:
                  last = mid - 1
              else:
                  first = mid + 1

      return False

  • 複雑さは最悪の場合O(nlogm)ですが、真ん中で見つけたらまあまあだと思いますが、試してみましたが、実は上のコードが似ています.
    • ドッキングデータ
    BOJ 159911、2、3プラス(6)