在 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

Arnab Chakraborty

更新于: 2020-08-25

466 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习