347. Top K Frequent Elements

,

Priority Queue

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
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Queue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));

        Map<Integer, Integer> numToFreqMap = new HashMap<>();
        for (int num : nums) {
            numToFreqMap.put(num, numToFreqMap.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : numToFreqMap.entrySet()) {
            int num = entry.getKey(), freq = entry.getValue();
            if (minHeap.size() < k || freq > minHeap.peek()[1]) {
                minHeap.offer(new int[]{num, freq});
            }
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        int[] res = new int[k];
        for (int j = 0; j < k; j++) {
            res[j] = minHeap.poll()[0];
        }
        return res;
    }
}

QuickSort

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
71
72
73
74
75
76
class Solution {
    private static class Element {
        private final int freq;
        private final int val;

        public Element(int freq, int val) {
            this.freq = freq;
            this.val = val;
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> valueToFreqMap = new HashMap<>();
        for (int num : nums) {
            valueToFreqMap.put(num, valueToFreqMap.getOrDefault(num, 0) + 1);
        }

        Element[] elements = new Element[valueToFreqMap.size()];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : valueToFreqMap.entrySet()) {
            elements[index++] = new Element(entry.getValue(), entry.getKey());
        }

        quickSort(elements, 0, elements.length - 1, k - 1);

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = elements[i].val;
        }

        return res;
    }

    private void quickSort(Element[] elements, int left, int right, int targetIndex) {
        if (left >= right) {
            return;
        }

        while (true) {
            int pivotIndex = partition(elements, left, right);
            if (pivotIndex < targetIndex) {
                left = pivotIndex + 1;
            } else if (pivotIndex > targetIndex) {
                right = pivotIndex - 1;
            } else {
                return;
            }
        }
    }

    private int partition(Element[] elements, int left, int right) {
        int randomIndex = left + ThreadLocalRandom.current().nextInt(right - left + 1);
        Element pivotElement = elements[randomIndex];
        swap(elements, left, randomIndex); // 注意此处是交换至 left 索引而不是 0
        
        int i = left, j = right;
        while (i < j) {
            while (i < j && elements[j].freq <= pivotElement.freq) {
                j--;
            }
            while (i < j && elements[i].freq >= pivotElement.freq) {
                i++;
            }
            swap(elements, i, j);
        }

        swap(elements, left, i); // 注意此处是交换至 left 索引而不是 0
        return i;
    }

    private void swap(Element[] elements, int i, int j) {
        Element tmp = elements[i];
        elements[i] = elements[j];
        elements[j] = tmp;
    }
}

References

347. Top K Frequent Elements
剑指 Offer II 060. 出现频率最高的 k 个数字