Python 中查詢重複陣列中丟失的元素

假設我們有兩個陣列，它們彼此重複，除了一個元素，因此，從給定的陣列中缺少一個元素，我們必須找到那個丟失的元素。

因此，如果輸入類似於 A = [2, 5, 6, 8, 10]，B = [5, 6, 8, 10]，則輸出將為 2，因為 2 在第二個陣列中丟失。

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

  • 定義一個函式 solve()。這將接收 A、B、N

  • 如果 N 等於 1，則

    • 返回 A[0];

  • 如果 A[0] 與 B[0] 不相同，則

    • 返回 A[0]

  • low := 0, high := N - 1

  • 當 low < high 時，執行

    • mid :=(low + high) / 2

    • 如果 A[mid] 與 B[mid] 相同，則

      • low := mid

    • 否則，

      • high := mid

    • 如果 low 等於 high - 1，則

      • 退出迴圈

  • 返回 A[high]

  • 從主方法中，執行以下操作：

  • M := A 的大小，N := B 的大小

  • 如果 N 等於 M-1，則

    • 返回 solve(A, B, M)

  • 否則，當 M 等於 N-1 時，則

    • 返回 solve(B, A, N)

  • 否則，

    • 返回“未找到”

示例

讓我們看看以下實現以獲得更好的理解：

 即時演示

def solve(A, B, N):
   if N == 1:
      return A[0];
   if A[0] != B[0]:
      return A[0]
   low = 0
   high = N - 1
   while (low < high):
      mid = (low + high) / 2
      if A[mid] == B[mid]:
         low = mid
      else:
         high = mid
      if low == high - 1:
         break
   return A[high]
def get_missing_element(A, B):
   M = len(A)
   N = len(B)
   if N == M-1:
      return solve(A, B, M)
   elif M == N-1:
      return solve(B, A, N)
   else:
      return "Not found"

A = [2, 5, 6, 8, 10]
B = [5, 6, 8, 10]
print(get_missing_element(A, B))

輸入

[2, 5, 6, 8, 10], [5, 6, 8, 10]

輸出

2

更新於: 2020年8月25日

241 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告

© . All rights reserved.