Cho mảng nums và số k. Xóa đúng k phần tử. Tìm số lượng giá trị khác nhau nhỏ nhất có thể đạt được.
Ví dụ: nums = [5,4,2,2,4,4,3], k = 3. Xóa 5, 3 và một trong {2,4} → chỉ còn 2 và 4 → kết quả 2.
Thuật toán giải quyết (Tham lam)
- Đếm tần suất mỗi số (dictionary).
- count := số giá trị khác nhau.
- Sắp xếp tần suất tăng dần. Duyệt từng tần suất f:
- k := k - f.
- Nếu k < 0: trả về count (không xóa hết được nhóm này).
- Ngược lại: count -= 1 (đã xóa hết một giá trị).
- Trả về count.
Ý tưởng: ưu tiên xóa hoàn toàn các giá trị có tần suất thấp nhất trước.
Ví dụ triển khai
def solve(nums, k):
dictionary = {}
for num in nums:
if num not in dictionary:
dictionary[num] = 1
else:
dictionary[num] += 1
count = len(dictionary)
for frequency in sorted(dictionary.values()):
k -= frequency
if k < 0:
return count
else:
count -= 1
return count
nums = [5,4,2,2,4,4,3]
k = 3
print(solve(nums, k))Đầu vào
[5,4,2,2,4,4,3], 3
Đầu ra
2