桶排序 1、出现频率最多的 k 个元素 347、Top K Frequent Elements (Medium)
Given [1,1,1,2,2,3] and k = 2, return [1,2].
实现思想：设置若干个桶，每个桶存储出现频率相同的数。桶的下标表示数出现的频率，即第 i 个桶中存储的数出现的频率为 i。把数都放到桶之后，从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数。
具体过程步骤：
1.第一步：采用map字典，统计同一个数字出现的次数；（这一步中关键是如何统计？）
将所给数字作为键（key）， 值（value）采用getOrDefault(key,default)函数，该函数意思是获取指定key的值，如果获取为空，则返回default（默认）值，这一步是关键；2.第二步：装桶,将键值对的 value 作为集合数组的下表，key 作为集合数组的值，从而实现桶排序；3.将题目要求的频率最多的 k 个元素存放在集合中,逆序进行；4.打印输出（或者return）结果。 代码实现：
package order;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;public class Order2_TopKFrequent { public static void main(String[] args) { //题目给出的数据 int[] nums = new int[]{1, 1, 1, 2, 2, 3}; //测试数据 //int[] nums = new int[]{1,3,1,2,3,3,3,2,1,3,2,1,2,3}; int k = 2; //1.第一步：采用map字典，统计同一个数字出现的次数 Map frequencyForNum = new HashMap<>(); for (int num : nums) { frequencyForNum.put(num, frequencyForNum.getOrDefault(num, 0) + 1); } //2.第二步：装桶,将键值对的 value 作为集合数组的下表，key 作为集合数组的值，从而实现桶排序 List[] buckets = new ArrayList[nums.length + 1]; for (int key : frequencyForNum.keySet()) { int frequency = frequencyForNum.get(key); if (buckets[frequency] == null) { buckets[frequency] = new ArrayList<>(); } buckets[frequency].add(key); System.out.println(buckets[frequency]); } //3.将题目要求的频率最多的 k 个元素存放在集合中,逆序进行 List topK = new ArrayList<>(); for (int i = buckets.length - 1; i >= 0 && topK.size() < k; i--) { if (buckets[i] == null) continue; //该步骤功能：防止出现 相同次数最多的元素时，造成返回结果超过 k 个元素 if (buckets[i].size() <= k - topK.size()) { topK.addAll(buckets[i]); } else { topK.addAll(buckets[i].subList(0, k - topK.size())); } for (int j : buckets[i]) { System.out.println("原数：" + j + " 出现次数：" + i); } } //4.输出结果 System.out.printf("出现次数最多的%d个数：n", k); for (int j = 0; j < topK.size(); j++) { System.out.print(topK.get(j) + " "); } }}