LeetCode291 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

你的名字 2020-11-14 08:08 731阅读 0赞

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

**示例 1:**

输入: nums = [1,1,1,2,2,3], k = 2
    输出: [1,2]

**示例 2:**

输入: nums = [1], k = 1
    输出: [1]

**说明：**

*  你可以假设给定的 *k *总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 *  你的算法的时间复杂度**必须**优于 O(*n* log *n*) , *n *是数组的大小。

解法：java桶排序实现--serpmelon

public List<Integer> topKFrequent(int[] nums, int k) {
            
            HashMap<Integer, Integer> map = new HashMap<>();
            for(int i : nums) { // 统计频率，key为元素，value为次数
                
                map.put(i, map.getOrDefault(i, 0) + 1);
            }
            
            // 创建nums.length + 1个桶
            List<Integer>[] bucket = new List[nums.length + 1];
            // 遍历map，根据value值放到对应的桶中
            for(Map.E***y<Integer, Integer> e : map.e***ySet()) {
                
                Integer value = e.getValue();
                if(bucket[value] == null) {
                    bucket[value] = new ArrayList<Integer>();
                }
                
                bucket[value].add(e.getKey());
            }
            
            List<Integer> freList = new ArrayList<>();
            // 桶的编号表示出现次数，所以倒数桶
            for(int j = bucket.length - 1; j > -1 && freList.size() < k; j--) {
                
                if(bucket[j] != null)
                    freList.addAll(bucket[j]);
            }
            
            return freList;
        }