在 Python 中查詢連續數字排序陣列中的缺失元素

假設我們有一個包含 n 個唯一數字的陣列 A，這 n 個元素按升序排列在陣列中，但缺少一個元素。我們需要找到缺失的元素。

因此，如果輸入類似於 A = [1, 2, 3, 4, 5, 6, 7, 9]，則輸出將為 8。

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

  • n := A 的大小

  • left := 0

  • right := n - 1

  • mid := 0

  • 當 right > left 時，執行以下操作：

    • mid := left +(right - left) / 2

    • 如果 A[mid] - mid 與 A[0] 相同，則：

      • 如果 A[mid + 1] - A[mid] > 1，則：

        • 返回 A[mid] + 1

      • 否則：

        • left := mid + 1

    • 否則：

      • 如果 A[mid] - A[mid - 1] > 1，則：

        • 返回 A[mid] - 1

      • 否則：

        • right := mid - 1

  • 返回 -1

示例

讓我們看看下面的實現以更好地理解：

 線上演示

def search_missing_item(A):
   n = len(A)
   left, right = 0, n - 1
   mid = 0
   while (right > left):
      mid = left + (right - left) // 2
   if (A[mid] - mid == A[0]):
      if (A[mid + 1] - A[mid] > 1):
         return A[mid] + 1
      else:
         left = mid + 1
      else:
         if (A[mid] - A[mid - 1] > 1):
            return A[mid] - 1
         else:
            right = mid - 1
   return -1

A = [1, 2, 3, 4, 5, 6, 7, 9]
print(search_missing_item(A))

輸入

[1, 2, 3, 4, 5, 6, 7, 9]

輸出

8

更新於: 2020-08-25

466 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告