主題: 學習筆記
LeetCode 347：TypeScript Top K Frequent Elements，從頻率排序到 bucket
先以 Map 計數後排序找出最高頻元素，再用 bucket 消除 O(n log n) 的排序成本。
這題我先用 Map 計算次數，再依頻率排序。這個版本能正確回傳答案，也是很合理的第一步。不過原題 follow-up 要求複雜度優於 O(n log n)，因此還要把完整排序換掉。
題目
對應原題：LeetCode 347：Top K Frequent Elements
給定整數陣列 nums 與整數 k，回傳出現頻率最高的 k 個元素。輸出順序不限。題目保證答案唯一，並要求 follow-up 解法的時間優於 O(n log n)。
暴力解會重複計數
最直接的做法是對每個元素再掃描一次整個陣列，計算它出現幾次，然後找出最高的 k 個。每個元素都可能重新走訪 nums，時間是 O(n²)。
先把每個數字的次數記起來，至少能把重複計數移除。
我最先寫的 Map 計數後排序解法
function topKFrequent(nums: number[], k: number): number[] {
if (k === 1 && nums.length === 1) return nums;
const map = new Map<number, number>();
for (let index = 0; index < nums.length; index += 1) {
const num = nums[index];
map.set(num, (map.get(num) ?? 0) + 1);
}
return [...map]
.sort((left, right) => right[1] - left[1])
.slice(0, k)
.map(([num]) => num);
}這是我最先寫的解法。第一個迴圈用 Map 記錄每個數字的次數。展開 Map 後得到 [數字, 次數] 陣列，依索引 1 的次數由大到小排序，取前 k 筆，再只回傳數字。
map[Symbol.iterator]() 也是合法的寫法，因為 Map 的預設 iterator 會產生 [key, value]。不過 [...map] 或 [...map.entries()] 較容易讀懂。MDN 的 Map 文件也說明 Map 的迭代會產生 key-value pairs。
k === 1 && nums.length === 1 的提前回傳不需要。一般流程已能正確處理單一元素。
這版的複雜度與限制
用 u 表示不同數字的數量，避免和題目參數 k 混淆。
- 計數：
O(n)。 - 將
Map展開：O(u)。 - 排序：
O(u log u)。 slice()與最後的map()：O(k)。
總時間是 O(n + u log u)，最壞情況 u = n 時就是 O(n log n)。所以這是可用的基準解，卻沒有滿足題目「優於 O(n log n)」的 follow-up。額外空間有 Map 與展開後的 entries，都是 O(u)；輸出另占 O(k)。
JavaScript 規格不保證 Array.prototype.sort() 的固定排序演算法或複雜度。面試裡通常以比較排序的 O(u log u) 分析，而 MDN 的 sort 文件也說實際複雜度由實作決定。
符合 follow-up 的 bucket 解法
元素的出現次數不會超過 nums.length。因此可以建立索引 0 到 n 的 buckets，讓 bucket 索引直接表示頻率，不必排序所有不同元素。
function topKFrequent(nums: number[], k: number): number[] {
const counts = new Map<number, number>();
for (const num of nums) {
counts.set(num, (counts.get(num) ?? 0) + 1);
}
const buckets: number[][] = Array.from(
{ length: nums.length + 1 },
() => [],
);
for (const [num, frequency] of counts) {
buckets[frequency].push(num);
}
const result: number[] = [];
for (let frequency = buckets.length - 1; frequency > 0; frequency -= 1) {
for (const num of buckets[frequency]) {
result.push(num);
if (result.length === k) return result;
}
}
return result;
}Array.from(..., () => []) 會為每個 bucket 建立不同陣列。不要寫成 new Array(nums.length + 1).fill([])，那會讓所有索引共用同一個陣列。
第一次走訪計數是 O(n)。將 u 個不同數字放入 bucket 是 O(u)，從頻率 n 往下掃描 buckets 加上取出元素最多也是 O(n + u)。總時間是 O(n)，額外空間是 buckets、Map 與輸出的 O(n)。這符合 follow-up。
正確性與迴圈不變量
計數迴圈處理完 nums[0..i] 後，counts.get(num) 等於 num 在這段前綴中出現的次數。
建立 buckets 後，每個不同數字恰好位於索引等於它最終頻率的 bucket。從高頻率往低頻率走訪時，result 只會加入尚未走到的頻率更低的元素之前的數字。當 result 長度達到 k，它包含的就是頻率最高的 k 個元素。
最小驗證
輸出順序不限，因此先排序結果再比較。
import assert from "node:assert/strict";
function sorted(values: number[]): number[] {
return [...values].sort((left, right) => left - right);
}
assert.deepStrictEqual(sorted(topKFrequent([1, 1, 1, 2, 2, 3], 2)), [1, 2]);
assert.deepStrictEqual(sorted(topKFrequent([1], 1)), [1]);
assert.deepStrictEqual(
sorted(topKFrequent([1, 2, 1, 2, 1, 2, 3, 1, 3, 2], 2)),
[1, 2],
);
assert.deepStrictEqual(sorted(topKFrequent([-1, -1, -1, 0, 0, 2], 1)), [-1]);常見陷阱
- 用不同元素數量也叫
k。題目已用k表示要回傳幾個元素，改用u表示 unique count。 - 認為計數後排序已符合 follow-up。排序所有不同元素仍可能是
O(n log n)。 - 用
fill([])建立 buckets，導致每個頻率共用同一個陣列。 - 回傳順序固定後才測試。題目允許任意順序，測試時應先排序。
- 用未加型別的
new Map()，讓 key 和 value 退成any。
可遷移的思路
當某個數值的範圍被輸入大小限制住時，bucket 可以取代比較排序。這題的頻率一定介於 1 到 n，因此頻率本身就能當索引。這個想法也會出現在 counting sort 和依頻率分層處理的問題。
外部參考連結
- LeetCode 347：Top K Frequent Elements：題目、限制與複雜度 follow-up。
- MDN：Map：
Map的 key-value pairs 與迭代行為。 - MDN：Array.prototype.sort()：
sort()的原地排序與實作相關複雜度。 - Node.js：assert.deepStrictEqual()：巢狀與陣列值的嚴格比較。