/
LeastNumberOfUniqueIntegersAfterKRemovals.java
66 lines (55 loc) · 1.77 KB
/
LeastNumberOfUniqueIntegersAfterKRemovals.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
// https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals/
class Solution {
public int findLeastNumOfUniqueInts(int[] arr, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x: arr) freq.put(x, freq.getOrDefault(x, 0) + 1);
List<Frequency<Integer>> freqList = Frequency.fromMap(freq);
Collections.sort(freqList);
for (int i = 0; i < freqList.size(); i++) {
var e = freqList.get(i);
if (e.canFullyConsume(k)) {
k -= e.freq;
e.consume();
} else {
e.consume(k);
if (e.freq == 0) {
return freqList.size() - i - 1;
} else {
return freqList.size() - i;
}
}
}
return 0;
}
static final class Frequency<T> implements Comparable<Frequency<T>> {
T val;
int freq;
Frequency(T val, int freq) {
this.val = val;
this.freq = freq;
}
void consume(int n) {
freq -= n;
if (freq < 0) freq = 0;
}
void consume() {
freq = 0;
}
boolean canFullyConsume(int k) {
return freq <= k;
}
public int compareTo(Frequency other) {
return this.freq - other.freq;
}
public String toString() {
return "{val=" + val + ", freq=" + freq + "}";
}
static <E> List<Frequency<E>> fromMap(Map<E, Integer> freq) {
List<Frequency<E>> list = new ArrayList<>();
for (var e: freq.entrySet()) {
list.add(new Frequency(e.getKey(), e.getValue()));
}
return list;
}
}
}