1、前言

2、思路

这道题不难，用 map 统计每个数字的 frequency 后，然后排序（nlogn）或者保持一个数量为 k 的小根堆（nlogk）就能解决。但是这不是终极解决方案，终极方案是使用桶排序。

桶排序是将要排序的数字落在一个桶内，这样落在不同桶内的数字天然有序，就是比较费空间而已。以此题为例，我们定义一个 nums.length + 1 的桶（利用 frequency 作为索引，如果只有一个数，索引为1，那么空间为 nums.length + 1）。map 统计完每个数字的 frequency 后，然后将相应的数字放到索引里。因为有相同的 frequency 有多个数，所以需要一个 list 来包裹。遍历完后再统计一遍即可。

3、代码

public class Q347_TopKFrequent {

    class Num{
        private int value;
        private int frequency;

        public Num(int value, int frequency) {
            this.value = value;
            this.frequency = frequency;
        }

        @Override
        public boolean equals(Object obj) {
            return ((Num)obj).value == this.value;
        }
    }

    /**
     * 普通的小根堆解法
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent2(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return null;
        }

        Map<Integer, Num> map = new HashMap<>();
        for (int num : nums) {
            if(map.containsKey(num)){
                Num n = map.get(num);
                n.frequency++;
                map.put(num, n);
            }else {
                map.put(num, new Num(num, 1));
            }
        }

        PriorityQueue<Num> priorityQueue = new PriorityQueue<>(new Comparator<Num>() {
            @Override
            public int compare(Num o1, Num o2) {
                return o1.frequency - o2.frequency;
            }
        });

        // nlogk，比 nlogn 没快多少
        for (Integer key : map.keySet()) {
            if(priorityQueue.size() < k){
                priorityQueue.add(map.get(key));
            }else if(map.get(key).frequency > map.get(priorityQueue.peek().value).frequency){
                priorityQueue.poll();
                priorityQueue.add(map.get(key));
            }
        }

        int[] res = new int[k];
        for(int i = 0; i < res.length; i++){
            res[i] = priorityQueue.poll().value;
        }

        return res;
    }

    public int[] topKFrequent(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return null;
        }

        Map<Integer, Num> map = new HashMap<>();
        for (int num : nums) {
            if(map.containsKey(num)){
                Num n = map.get(num);
                n.frequency++;
                map.put(num, n);
            }else {
                map.put(num, new Num(num, 1));
            }
        }

        // 桶排序，将 frequency 作为数组 index，value 作为数组的值
        List<Integer>[] total = new ArrayList[nums.length + 1];
        for (Integer key : map.keySet()) {
            Num num = map.get(key);
            if(total[num.frequency] == null){
                total[num.frequency] = new ArrayList<>();
            }
            total[num.frequency].add(num.value);
        }

        int[] res = new int[k];
        // 桶排序后，frequency 大的都在数组后面
        for(int i = 0, j = total.length - 1; i < k && j >= 0;j--){
            if(total[j] != null){
                for (Integer num : total[j]) {
                    if(i >= k){
                        return res;
                    }
                    res[i++] = num;
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2};
        int k = 2;
        int[] res = new Q347_TopKFrequent().topKFrequent(nums, k);
        for (int re : res) {
            System.out.println(re);
        }
    }
}