題目描述:給定整數陣列,找出出現頻率最高的前 k 個元素。
解題思路:桶排序(Bucket Sort)O(n) 解法:先統計每個元素的頻率,再建立以頻率為索引的桶(大小為 n+1)。從高頻到低頻遍歷桶,收集元素直到湊滿 k 個。由於頻率範圍是 1 到 n,桶的大小固定,整體 O(n)。
時間複雜度: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 個最小堆(每個頻率層級)— 邏輯複雜,無益。