【每日一题】LeetCode 347. 前 K 个高频元素 TypeScript

给你一个整数数组nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。

示例 1：

输入：nums = [1,1,1,2,2,3], k = 2

输出：[1,2]

示例 2：

输入：nums = [1], k = 1

输出：[1]

示例 3：

输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2

输出：[1,2]

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k的取值范围是[1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前k个高频元素的集合是唯一的

哈希表+桶排序

1.建哈希表：统计每个数字出现的次数 {1，3} 表示1出现了3次；

2.桶：数组下标是每个数字出现的次数，值是数字（可以是多个数出现的次数是相同的）；

3.往后遍历桶，把后k个加入列表中；

function topKFrequent(nums: number[], k: number): number[] { const map = new Map<number,number>() nums.forEach(item=>{ map.set(item,(map.get(item)||0)+1) }) const bucket = Array.from({length:nums.length+1},()=>[]) for(const [num,count] of map.entries()){ bucket[count].push(num) } const res:number[] = [] for(let i=bucket.length-1;res.length<k;i--){ if(bucket[i].length>0){ res.push(...bucket[i]) } } return res };

共勉