Chương trình tìm số nguyên dương thiếu thứ k trong mảng Python

Cho mảng nums tăng dần các số nguyên dương và số nguyên k. Tìm số nguyên dương thứ k bị thiếu trong mảng.

Ví dụ: nums = [1,2,4,8,12], k = 6 → 10 (các số thiếu: [3,5,6,7,9,10,11], số thứ 6 là 10).

Thuật toán

• Chuyển nums thành tập hợp (set) để tra cứu O(1).
• Khởi tạo count = 0, num = 1.
• Trong khi count < k:
• Nếu num không trong tập hợp, tăng count.
• Nếu count == k, trả về num.
• Tăng num lên 1.
• Trả về num.

Ví dụ (Python)

def solve(nums, k):
    nums = set(nums)
    count = 0
    num = 1
    while count < k:
        if num not in nums:
            count += 1
        if count == k:
            return num
        num += 1
    return num

nums = [1,2,4,8,12]
k = 6
print(solve(nums, k))

Đầu vào

[1,2,4,8,12], 6

Đầu ra

10