在 Python 中从重复数组中查找丢失的元素

pythonserver side programmingprogramming更新于 2025/10/10 14:36:17

假设我们有两个数组,除了一个元素外,它们彼此重复,因此,给定数组中的一个元素丢失了,我们必须找到那个丢失的元素。

因此,如果输入为 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 := size of A, N := B 的大小

  • 如果 N 与 M-1 相同,则

    • 返回 resolve(A, B, M)

  • 否则,当 M 与 N-1 相同时,则

    • 返回 resolve(B, A, N)

  • 否则,

    • 返回 "Not found"

示例

让我们看看下面的实现以便更好地理解 −

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

相关文章


有用资源