Star

LeetCode 347. Top K Frequent Elements

Posted on | In |

Question:

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.

Explanation

用了三种方法，桶排序，maxHeap以及TreeMap。主要是计算frequency，然后对frequency进行排序。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class Solution {
    // use hashmap && array
    // public List<Integer> topKFrequent(int[] nums, int k) {
    //     List<Integer> result = new ArrayList<>();
    //     Map<Integer, Integer> map = new HashMap<>();
    //     for(int n: nums){
    //         map.put(n, map.getOrDefault(n,0)+1);
    //     }
    //     // corner case: if there is only one number in nums, we need the bucket has index 1.
    //     List<Integer>[] bucket = new List[nums.length + 1];
    //     for(int key : map.keySet()) {
    //         int freq = map.get(key);
    //         if (bucket[freq] == null) {
    //             bucket[freq] = new LinkedList<>();
    //         }
    //         bucket[freq].add(key);
    //     }
    //     List<Integer> res = new LinkedList<>();
    //     for(int i=bucket.length-1; i>0 && k > 0; i--) {
    //         if(bucket[i]!=null) {
    //             result.addAll(bucket[i]);
    //             k -= bucket[i].size();
    //         }
    //     }
    //     return result;
    // }
    // use maxHeap
    // public List<Integer> topKFrequent(int[] nums, int k) {
    //     Map<Integer, Integer> map = new HashMap<>();
    //     for(int n: nums){
    //         map.put(n, map.getOrDefault(n,0)+1);
    //     }
    //     PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = new PriorityQueue<>((a,b) -> (b.getValue() - a.getValue()));
    //     for (Map.Entry<Integer, Integer> entry: map.entrySet()){
    //         maxHeap.add(entry);
    //     }
    //     List<Integer> result = new ArrayList<>();
    //     while(result.size()<k) {
    //         result.add(maxHeap.poll().getKey());
    //     }
    //     return result.subList(0, k);
    //  }
    // Use treeMap, use the frequency as the key so we can get all frequencies in order
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int n: nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }
        TreeMap<Integer, List<Integer>> treeMap = new TreeMap<>();
        for(int num: map.keySet()) {
            int freq = map.get(num);
            if(!treeMap.containsKey(freq)){
                treeMap.put(freq, new ArrayList<>());
            }
            treeMap.get(freq).add(num);
        }
        List<Integer> result = new ArrayList<>();
        while(result.size()<k) {
            Map.Entry<Integer, List<Integer>> entry = treeMap.pollLastEntry();
            result.addAll(entry.getValue());
        }
        return result.subList(0, k);
    }
}