Chương trình tìm k nơi có đúng k phần tử lớn hơn hoặc bằng k trong Python

Cho danh sách nums chỉ chứa số không âm. Tìm k sao cho có đúng k phần tử ≥ k. Nếu không tồn tại, trả về -1.

Ví dụ: nums = [6, 4, 0, 8, 2, 9] → kết quả 4. Có 4 phần tử ≥ 4: [6, 4, 8, 9].

Thuật toán giải quyết (O(n log n))

1. Sắp xếp nums giảm dần
2. Duyệt i từ 1 đến len(nums)-1:
   • Nếu i > nums[i-1]: dừng (không thể có k = i)
   • Nếu i > nums[i]: trả về i (tìm thấy k)
3. Trả về -1 nếu không tìm thấy

Lý do: sau khi sắp xếp giảm, nums[i-1] là phần tử thứ i lớn nhất. Nếu i > nums[i] nghĩa là có đúng i phần tử ≥ i.

Ví dụ minh họa

def solve(nums):
    nums.sort(reverse=True)
    for i in range(1, len(nums)):
        if i > nums[i-1]:
            break
        elif i > nums[i]:
            return i
    return -1

nums = [6, 4, 0, 8, 2, 9]
print(solve(nums))

Đầu vào

[6, 4, 0, 8, 2, 9]

Đầu ra

4