在 Python 中查找连续数字排序数组中缺失的元素

假设我们有一个包含 n 个唯一数字的数组 A，这 n 个元素按升序排列在数组中，但有一个缺失的元素。我们必须找到缺失的元素。

因此，如果输入为 A = [1, 2, 3, 4, 5, 6, 7, 9]，则输出为 8。

为了解决这个问题，我们将遵循以下步骤 −

• n := A 的大小

• left := 0

• right := n - 1

• mid := 0

• while 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
  

  ---

  相关文章

  • Python 中通过 K 扩展列表
  • Python - 使用交替的 0 和 1 初始化列表
  • Python 中元组列表到字典的转换
  • Python - 从两个列表中配对，使得成对的元素不相同
  • 使用 Python 和 SQLite 的 SQL
  • 使用 pytrie 模块在 Python 中进行前缀匹配
  • 创建和访问 Python 包
  • 如何使用正则表达式和数据类型选择多个 DataFrame 列
  • 如何在 Pandas 中查找和过滤重复行?
  • 用 Python 编写程序以正确的顺序查找机场?

  ---

  有用资源

  • python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

  ---

  打印 下一节:在 Python 中查找 N 个按位或等于 K 的不同数字 ❯❮ 上一节:在 Python 中找出完成所有给定约束条件的工作的最短时间