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] > 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

更新于： 28-4-2020

340 次浏览

开启你的 职业生涯

完成课程即可获得认证

开始
广告