Python中缺少数字

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

为了解决这个问题,我们将使用二进制搜索方法。

  • 按升序对列表进行排序

  • 高= A的长度,低= 0

  • 从低到高,做

    • 低=中+ 1

    • 高=中

    • 中=低+(高–低)/ 2

    • 如果A [mid]> mid

    • 除此以外

    • 返回低

    示例

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

    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