Python 中的缺失数字

假设我们有一个从 0 到 n 的数字列表。有一个数字缺失。我们必须以一种有效的方法找到缺失的数字。因此，如果 A = [0, 1, 2, 3, 4, 5, 7, 8, 9]，则缺失数字为 6。

为了解决这个问题，我们将使用二分搜索方法。

• 按升序对列表进行排序
• high = A 的长度，low = 0
• 当 low < high 时，执行
  • mid = low + (high – low)/2
  • 如果 A[mid] >中
    • high = mid
  • 否则
    • low = mid + 1
  • 返回 low

  示例

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

  class Solution(object):
     def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        high = len(nums)
        low = 0
        while low<high:
           mid = low + (high-low)//2
           if nums[mid]>mid:
              high = mid
           else:
              low = mid+1
        return low
  ob1 = Solution()
  print(ob1.missingNumber([5,3,1,7,8,0,9,2,4]))
  

  输入

  nums = [5,3,1,7,8,0,9,2,4]
  

  输出

  6
  

  ---

  相关文章

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

  ---

  有用资源

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

  ---

  打印 下一节:在 Python 中移动零 ❯❮ 上一节:Python 中的有效字谜