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