    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<Map.Entry<Integer,Integer>> list = new ArrayList<>(countMap.entrySet()); 
        Collections.sort(list, (a,b)->(b.getValue() - a.getValue()));

        // topk
        int[] res = new int[k];
        for(int i = 0; i < k; i++) {
            res[i] = list.get(i).getKey();
        }    
        return res;
    }

效果

13ms 15.58%

复杂度

时间复杂度：O(n log n)（排序）

空间复杂度：O(n)

反思

这个解法简单粗暴，符合直觉。

很好。

v2-HashMap + 优先级队列

思路

借助 HashMap 统计，然后借助优先级队列处理

实现

    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);
        }

        // 小顶堆，堆里存 [数字, 频率]
        // 小的放在上面 然后丢掉，留下的就是大的
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b)->(a[1]-b[1]));
        for(Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            Integer key = entry.getKey();
            Integer count = entry.getValue();
            heap.offer(new int[]{key, count});
        }
        // 丢弃
        while(heap.size() > k) {
            heap.poll();
        }

        int[] res = new int[k];
        int ix = 0;
        while(!heap.isEmpty()) {
            res[ix++] = heap.poll()[0];
        }
        return res;
    }

效果

13ms 击败 64.18%

复杂度

时间复杂度：O(n log k)

空间复杂度：O(n)

v3-桶排序

思路

这里最核心的除了统计，就是排序了。

如果我们可以针对排序从 O(n*logn)->O(n) 也是一种提升。

1）我们直接在 v1 的基础上修改，用桶排序来替代。

2）逆序设置即可

实现

    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<Integer>[] bucket = new List[nums.length + 1];
        for (int key : countMap.keySet()) {
            int freq = countMap.get(key);
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(key);
        }
        
        // topk
        int[] res = new int[k];
        int count = 0;
        for(int i = bucket.length-1; i >= 0; i--) {
            List<Integer> freqNums = bucket[i];
            if(freqNums != null) {
                for(Integer num : freqNums) {
                    res[count++] = num;
                    if(count >= k) {
                        return res;
                    }
                }
            }
        }    
        return res;
    }