- Notifications
You must be signed in to change notification settings - Fork 1.3k
/
Copy path_1338.java
53 lines (50 loc) · 1.57 KB
/
_1338.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
packagecom.fishercoder.solutions.secondthousand;
importjava.util.ArrayList;
importjava.util.Collections;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;
publicclass_1338 {
publicstaticclassSolution1 {
publicintminSetSize(int[] arr) {
Map<Integer, Integer> map = newHashMap<>();
for (inti : arr) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
List<Integer> list = newArrayList<>();
for (intk : map.keySet()) {
list.add(map.get(k));
}
Collections.sort(list, Collections.reverseOrder());
intsum = 0;
inti = 0;
while (sum < arr.length / 2) {
sum += list.get(i++);
}
returni--;
}
}
publicstaticclassSolution2 {
publicintminSetSize(int[] arr) {
Map<Integer, Integer> map = newHashMap<>();
for (intnum : arr) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
List<int[]> list = newArrayList<>();
for (intkey : map.keySet()) {
list.add(newint[] {map.get(key), key});
}
Collections.sort(list, (a, b) -> b[0] - a[0]);
intminSet = 0;
intcount = 0;
for (int[] pair : list) {
count += pair[0];
minSet++;
if (count >= arr.length / 2) {
returnminSet;
}
}
returnminSet;
}
}
}