โจทย์: กำหนดอาร์เรย์จำนวนเต็มและค่า k ให้คืนค่า k องค์ประกอบที่มีความถี่มากที่สุด
ตัวอย่าง
Input: nums = [1,1,1,1,2,2,3,3,3], k = 2 Output: [1, 3]
แนวคิด (Bucket Sort)
- นับความถี่แต่ละตัวเลข → dict
num_freq - กลุ่มตัวเลขตามความถี่ → dict
freq_list(key=ความถี่, value=ลิสต์ตัวเลข) - วนจากความถี่สูงสุดลงมา เก็บผลลัพธ์จนครบ k ตัว
โค้ด
class Solution:
def topKFrequent(self, nums, k):
num_freq = {}
for n in nums:
num_freq[n] = num_freq.get(n, 0) + 1
freq_list = {}
for num, freq in num_freq.items():
freq_list.setdefault(freq, []).append(num)
res = []
for freq in range(len(nums), 0, -1):
if freq in freq_list:
res.extend(freq_list[freq])
if len(res) >= k:
break
return res[:k]
# ทดสอบ
sol = Solution()
print(sol.topKFrequent([1,1,1,1,2,2,3,3,3], 2)) # [1, 3]
ความซับซ้อน
- Time: O(n)
- Space: O(n)
สรุป
Bucket sort ให้คำตอบ O(n) ดีกว่า sorting ทั่วไปที่ O(n log n)
