Description

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.

Solution

HashMap and Bucket Sort, time O(n), space O(n)

算法大致是这样的：

• 首先用一个Map存储数组中每个value出现的次数；
• 之后由于要求k个，由于数组中每个value出现的次数都是[1, n]范围之内的，所以可以用一个大小为n的bucket，对每个次数对应的value做记录。
• 逆向遍历bucket输出即可。

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> valToCount = new HashMap<>();
        
        for (int n : nums) {
            valToCount.put(n, valToCount.getOrDefault(n, 0) + 1);
        }
        
        // bucket[count] = value list with the count
        List<Integer>[] bucket = new ArrayList[nums.length + 1];
        for (int n : valToCount.keySet()) {
            if (bucket[valToCount.get(n)] == null) {
                bucket[valToCount.get(n)] = new ArrayList<>();
            }
            bucket[valToCount.get(n)].add(n);
        }
        
        List<Integer> topKFrequent = new LinkedList<>();
        for (int i = nums.length; i > 0 && k > 0; --i) {
            if (bucket[i] == null) {
                continue;
            }
            
            for (int j = 0; j < bucket[i].size() && k-- > 0; ++j) {
                topKFrequent.add(bucket[i].get(j));
            }
        }
        
        return topKFrequent;
    }
}

Maxheap, time O(nlogn), space O(n)

可以用PriorityQueue实现一个Maxheap。

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> valToCount = new HashMap<>();
        
        for (int n : nums) {
            valToCount.put(n, valToCount.getOrDefault(n, 0) + 1);
        }
        
        PriorityQueue<Map.Entry<Integer, Integer>> maxHeap 
            = new PriorityQueue<>(nums.length, 
                                  new Comparator<Map.Entry<Integer, Integer>>() {
                public int compare(Map.Entry<Integer, Integer> a
                                   , Map.Entry<Integer, Integer> b) {
                    return b.getValue() - a.getValue();
                } 
            });
        
        maxHeap.addAll(valToCount.entrySet());
        
        List<Integer> topKFrequent = new LinkedList<>();
        while (k-- > 0) {
            topKFrequent.add(maxHeap.poll().getKey());
        }
        
        return topKFrequent;
    }
}