Số bị thiếu trong Python

Cho danh sách số từ 0 đến n, thiếu một số. Tìm số thiếu hiệu quả. Ví dụ: [0,1,2,3,4,5,7,8,9] → 6.

Giải pháp

Tìm kiếm nhị phân:

• Sắp xếp mảng.
• high = len(A), low = 0.
• Trong khi low < high: mid = low + (high-low)//2. Nếu A[mid] > mid → high = mid; else low = mid+1.
• Trả về low.

Ví dụ

Triển khai Python:

class Solution(object): 
    def missingNumber(self, nums): 
        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