MediumRating 1540
347. Top K Frequent Elements
arrayhash-tabledivide-and-conquersortingheap-priority-queuebucket-sortcountingquickselect
解題說明
Top K Frequent Elements
題目描述：給定整數陣列，找出出現頻率最高的前 k 個元素。
解題思路：桶排序（Bucket Sort）O(n) 解法：先統計每個元素的頻率，再建立以頻率為索引的桶（大小為 n+1）。從高頻到低頻遍歷桶，收集元素直到湊滿 k 個。由於頻率範圍是 1 到 n，桶的大小固定，整體 O(n)。
C++ 解法
複雜度分析
時間複雜度：O(n) — 計頻、填桶、收集各 O(n)。
空間複雜度：O(n) — 頻率表和桶陣列。
虛擬碼
1. Count frequency of each element 2. Create buckets[0..n] where buckets[f] = list of elements with frequency f 3. For f from n down to 1: a. Add elements in buckets[f] to result b. Stop when result has k elements 4. Return result
其他解法
排序 O(n log n) 時間，O(n) 空間：按頻率排序，取前 k 個 — 時間複雜度更差。
多個堆 O(n log k) 時間：維護 k 個最小堆（每個頻率層級）— 邏輯複雜，無益。
延伸思考
- 若 k 大於不同元素數？
- 如何在流式資料中更新前 k 個？
- 若要找前 k 頻繁的子序列？