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

Arnab Chakraborty

更新於： 28-4-2020

340 次瀏覽

開啟你的 職業生涯

完成課程即可獲得認證

開始