forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 1
/
347-Top-K-Frequent-Elements.java
91 lines (79 loc) · 2.34 KB
/
347-Top-K-Frequent-Elements.java
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class Solution1 {
/**
* Time Complexity: O(nlog(k))
* Space Complexity: O(n)
*/
public int[] topKFrequent(int[] nums, int k) {
int[] arr = new int[k];
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
(a, b) ->
a.getValue() - b.getValue()
);
for (Map.Entry<Integer, Integer> it : map.entrySet()) {
pq.add(it);
if (pq.size() > k) pq.poll();
}
int i = k;
while (!pq.isEmpty()) {
arr[--i] = pq.poll().getKey();
}
return arr;
}
}
class Solution2 {
/**
* Time Complexity: O(n)
* Space Complexity: O(n)
*/
public int[] topKFrequent(int[] numbers, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int number : numbers) map.put(
number,
map.getOrDefault(number, 0) + 1
);
int size = map.size();
int[] keys = new int[size];
int i = 0;
for (int key : map.keySet()) keys[i++] = key;
select(keys, map, 0, size - 1, size - k);
return Arrays.copyOfRange(keys, size - k, size);
}
// Modified implementation of Hoare's selection algorithm:
private void select(
int[] keys,
Map<Integer, Integer> map,
int left,
int right,
int kSmallest
) {
while (left != right) {
int pivot = partition(keys, map, left, right, (left + right) / 2);
if (kSmallest == pivot) return;
if (kSmallest < pivot) right = pivot - 1; else left = pivot + 1;
}
}
private int partition(
int[] keys,
Map<Integer, Integer> map,
int left,
int right,
int pivot
) {
int pivotValue = map.get(keys[pivot]);
swap(keys, pivot, right);
int index = left;
for (int i = left; i <= right; i++) if (map.get(keys[i]) < pivotValue) {
swap(keys, i, index);
index++;
}
swap(keys, right, index);
return index;
}
private void swap(int[] array, int i1, int i2) {
int temp = array[i1];
array[i1] = array[i2];
array[i2] = temp;
}
}