347. 前 K 个高频元素 - 力扣（LeetCode）

/**

        桶排序:

                首先遍历数组,使用HashMap统计每个元素出现的次数

                创建一个大小为length + 1的List数组,下标代表元素出现次数,出现次数一致的元素放在同一个数组中

                倒数遍历List数组即可得得到前K个高频元素

        细节注意:

                长度为length的数组,可能存储的元素全部相同,则最高频元素出现次数为length

                下标代表频率即元素出现次数,则List数组大小需为length + 1

*/

class Solution {/**桶排序:首先遍历数组,使用HashMap统计每个元素出现的次数创建一个大小为length + 1的List数组,下标代表元素出现次数,出现次数一致的元素放在同一个数组中倒数遍历List数组即可得得到前K个高频元素细节注意:长度为length的数组,可能存储的元素全部相同,则最高频元素出现次数为length下标代表频率即元素出现次数,则List数组大小需为length + 1*/public int[] topKFrequent(int[] nums, int k) {//统计元素出现次数Map<Integer,Integer> countMap = new HashMap<>();for(int num : nums) {countMap.put(num,countMap.getOrDefault(num,0) + 1);}//创建List数组,按照出现次数,将元素存入List数组中List<Integer>[] buckets = new ArrayList[nums.length + 1];for(int num : countMap.keySet()) {//读取当前num的频率int freq = countMap.get(num); //将元素添加到对应的“频率桶中”if(buckets[freq] == null) {buckets[freq] = new ArrayList<>();}buckets[freq].add(num);}//倒序遍历频率桶收集结果int[] result = new int[k];int index = 0; //result填充位置for(int i = buckets.length - 1; i >= 0 && index < k; i--) {if(buckets[i] != null) {for(int num : buckets[i]) {result[index] =  num;index++;if(index == k) {break;}}}}return result;}
}