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

Arnab Chakraborty

更新于: 2020年8月25日

241 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始