Thiếu số trong Python

Giả sử chúng ta có một danh sách các số từ 0 đến n. Có một số bị thiếu. Chúng ta phải tìm số còn thiếu trong một cách tiếp cận hiệu quả. Vì vậy, nếu A =[0, 1, 2, 3, 4, 5, 7, 8, 9], số còn thiếu là 6.

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng phương pháp tìm kiếm nhị phân.

• sắp xếp danh sách theo thứ tự tăng dần
• cao =độ dài của A và thấp =0
• while low
• mid =low + (high - low) / 2
• nếu A [giữa]> giữa
  • cao =trung bình
• nếu không thì
  • thấp =giữa + 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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

Đầu vào

nums = [5,3,1,7,8,0,9,2,4]

Đầu ra

6