347. Top K Frequent Elements

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

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

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.

1.BucketSort

用frequencyMap统计每个数字出现的频率，然后将这些数字按出现频率添加到对应的桶中，最后从桶中由大到小取出k个数字。时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> result = new ArrayList<>(k);
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            frequencyMap.put(nums[i],  frequencyMap.getOrDefault(nums[i], 0) + 1);
        }

        List<Integer>[] bucket = new LinkedList[nums.length + 1];
        for (Integer key : frequencyMap.keySet()) {
            Integer count = frequencyMap.get(key);
            if (bucket[count] == null) bucket[count] = new LinkedList<>();
            bucket[count].add(key);
        }

        int count = 0;
        for (int i = nums.length; count < k && i >= 0; i--) {
            if (bucket[i] != null) {
                result.addAll(bucket[i]);
                count += bucket[i].size();
            }
        }
        return result;
    }
}

2.HeapSort

和上面桶排序的前半部分相同，最后将frequencyMap的结果写入到一个Heap中，Heap中包含了topK个数字。由于堆的插入排序耗时，所以时间复杂度为O(n logn)

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> result = new ArrayList<>(k);
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            frequencyMap.put(nums[i],  frequencyMap.getOrDefault(nums[i], 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
            public int compare(Map.Entry<Integer, Integer> e1, Map.Entry<Integer, Integer> e2) {
                return e2.getValue() - e1.getValue();
            }
        });

        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            heap.offer(entry);
        }

        for (int i = 0; i < k; i++) {
            result.add(heap.poll().getKey());
        }

        return result;
    }
}