มีรายการ items (ID สินค้า) และ n จำนวนที่ขายได้ หา ID ที่แตกต่างกันน้อยที่สุดหลังขาย n ชิ้น
เช่น items=[2,2,6,6], n=2 ให้ 1 (ขาย 2 ตัว ID 2 หรือ 6 เหลือ ID เดียว)
ขั้นตอนการแก้ปัญหา
- นับความถี่แต่ละ ID ใน
c ans = จำนวน ID ที่แตกต่างกัน- เรียงความถี่น้อยไปมาก
- ลบความถี่น้อยสุดออกจนกว่า n จะหมด ลด ans ทีละ 1
- คืนค่า ans
ตัวอย่างโค้ด
from collections import Counter
class Solution:
def solve(self, items, n):
c = Counter(items)
ans = len(c)
freq = sorted(c.values())
i = 0
while i < len(freq):
if freq[i] <= n:
n -= freq[i]; ans -= 1
else: return ans
i += 1
return 0
ob = Solution()
items = [2,2,6,6]; n = 2
print(ob.solve(items, n))
อินพุต
[2, 2, 6, 6], 2
เอาต์พุต
1
