Chương trình tìm số thiếu thứ K từ danh sách đã sắp xếp trong Python

Cho danh sách đã sắp xếp, các số duy nhất, và số . Tìm số thiếu thứ (0-indexed) tính từ phần tử đầu tiên.

Ví dụ: , → kết quả 9 (số thiếu: 7, 9 → index 1 là 9).

Giải thuật (Duyệt một lần O(n))

1. Duyệt từ 1 đến :
   • (số lượng số thiếu giữa 2 phần tử).
   • Nếu = diff: .
   • Ngược lại: trả về .
2. Nếu duyệt hết mà chưa trả về: số thiếu nằm sau phần tử cuối → .

Ví dụ minh họa

class Solution:
    def solve(self, nums, k):
        for i in range(1, len(nums)):
            diff = nums[i] - nums[i - 1] - 1
            if k >= diff:
                k -= diff
            else:
                return nums[i - 1] + k + 1
        return nums[-1] + k + 1

ob = Solution()
nums = [5, 6, 8, 10, 11]
k = 1
print(ob.solve(nums, k))  # Output: 9

Đầu vào

[5,6,8,10,11], 1

Đầu ra

9