Skip to main content

347. Top K Frequent Elements

分析

https://leetcode.cn/problems/top-k-frequent-elements/

https://www.youtube.com/watch?v=YPTqKIgVk-k&t=1s

题解

记录频率的桶排序

function topKFrequent(nums: number[], k: number): number[] {
// [1,1,1,2,2,3]
const memo: Record<number, number> = {}
for (const num of nums) {
if (!memo[num]) {
memo[num] = 0
}
memo[num] = memo[num] + 1
}
// memo
// {
// 1: 3,
// 2: 2,
// 3: 1
// }

// 显示分配 / 提示
const freqArray: number[][] = Array.from({ length: nums.length + 1 }, () => [])
for (const num in memo) {
const freq = memo[num]
freqArray[freq].push(Number(num))
}
// freqArray
// [, [3], [2], [3]]
const ans = []

for (let i = freqArray.length - 1; i > 0; i--) {
for (const num of freqArray[i]) {
ans.push(num)
if (ans.length === k) {
return ans
}
}
}

return ans
};