Python程式查詢給定矩陣中是否存在目標值

假設我們有一個二維矩陣，其中每一行和每一列都按非遞減順序排序，我們需要檢查給定的目標值是否在其中。

因此，如果輸入如下所示：

2430
3431
6632

並且目標值為 31，則輸出為 True

為了解決這個問題，我們將遵循以下步驟：

  • col := 矩陣列數 - 1
  • 對於 i 從 0 到矩陣行數，執行以下操作：
    • 當 matrix[i, col] > target 且 col >= 0 時，執行以下操作：
      • col := col - 1
    • 如果 matrix[i, col] 等於 target，則：
      • 返回 True
  • 返回 False

讓我們看一下以下實現，以便更好地理解：

示例

 即時演示

class Solution:
   def solve(self, matrix, target):
      col = len(matrix[0]) - 1
      for i in range(len(matrix)):
         while matrix[i][col] > target and col >= 0:
            col = col - 1
         if matrix[i][col] == target:
            return True
      return False
ob = Solution()
matrix = [ [2, 4, 30], [3, 4, 31], [6, 6, 32] ]
target = 31
print(ob.solve(matrix, target))

輸入

matrix = [
[2, 4, 30],
[3, 4, 31],
[6, 6, 32]]
target = 31

輸出

True

更新時間： 2020年11月20日

355 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告