数组中出现频率为k次的元素 Top K Frequent Elements

问题：

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note: 

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

解决：

①  使用map记录出现的次数，并根据map的值进行降序排序。时间O(n log n)，空间O（n）

class Solution { //30ms
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0;i < nums.length;i ++){
            map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
        }
        List<Map.Entry<Integer,Integer>> tmp = new ArrayList<>(map.entrySet());
        Collections.sort(tmp, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());//降序
            }
        });
        int count = 0;
        for (Map.Entry<Integer,Integer> entry : tmp){
            count ++;
            if (count > k) break;
            res.add(entry.getKey());
        }
        return res;
    }
}

② 桶排序。以[6 2 4 1 5 9]为例。

准备10个空桶,最大数个空桶。

1,顺序从待排数组中取出数字,首先6被取出,然后把6入6号桶,这个过程类似这样:空桶[ 待排数组[ 0 ] ] = 待排数组[ 0 ]

[6 2 4 1 5 9]           待排数组

[0 0 0 0 0 0 6 0 0 0]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

2,顺序从待排数组中取出下一个数字,此时2被取出,将其放入2号桶,是几就放几号桶

[6 2 4 1 5 9]           待排数组

[0 0 2 0 0 0 6 0 0 0]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

3,4,5,6省略,过程一样,全部入桶后变成下边这样

[6 2 4 1 5 9]           待排数组

[0 1 2 0 4 5 6 0 0 9]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

1,桶排序是稳定的

2,桶排序是常见排序里最快的一种,比快排还要快…大多数情况下

3,桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法

class Solution { //13ms
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        int max = 1;//记录最大出现次数
        int count = 1;//记录出现次数
        for (int i = 1;i < nums.length;i ++){
            if (nums[i] == nums[i - 1]){
                count ++;
                max = Math.max(max,count);
            }else {
                count = 1;
            }
        }
        List<Integer>[] bucket = new ArrayList[max + 1];
        count = 1;
        for (int i = 1;i < nums.length + 1;i ++){
            if (i < nums.length && (nums[i - 1] == nums[i])){
                count ++;
            }else {
                if (bucket[count] == null){
                    bucket[count] = new ArrayList<>();
                }
                bucket[count].add(nums[i - 1]);
                count = 1;
            }
        }
        count = 0;
        for (int i = max;i >= 1;i --){
            List<Integer> tmp = bucket[i];
            while(tmp != null && ! tmp.isEmpty()){
                res.add(tmp.remove(0));
                count ++;
                if (count == k) break;
            }
            if(count == k) break;
        }
        return res;
    }
}