假设我们有一个从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