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
| class Solution {
public int minSetSize(int[] arr) {
Map<Integer, Integer> numCount = new HashMap<>();
int maxCount = 0;
for (int num : arr) {
numCount.put(num, numCount.getOrDefault(num, 0) + 1);
maxCount = Math.max(maxCount, numCount.get(num));
}
List<List<Integer>> bucket = new ArrayList<>();
for (int i = 0; i <= maxCount; i++) {
bucket.add(new ArrayList<>());
}
for (Map.Entry<Integer, Integer> entry : numCount.entrySet()) {
int num = entry.getKey();
int count = entry.getValue();
bucket.get(count).add(num);
}
int remain = arr.length;
int removedCount = 0;
for (int i = bucket.size() - 1; i >= 0; i--) {
for (int num : bucket.get(i)) {
if (remain > arr.length / 2) {
removedCount += 1;
remain -= i;
} else {
break;
}
}
if (remain <= arr.length / 2) {
break;
}
}
return removedCount;
}
}
|
bucket sort.
时间复杂度: O(n)
空间复杂度: O(n) 创建了map, 以及list, list还装了buckets.
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
| class Solution {
private static class Pair {
int num;
int count;
Pair(int _num, int _count) {
num = _num;
count = _count;
}
}
public int minSetSize(int[] arr) {
Map<Integer, Pair> numCount = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
numCount.putIfAbsent(arr[i], new Pair(arr[i], 0));
numCount.get(arr[i]).count += 1;
}
List<Pair> list = new ArrayList<>();
for (Map.Entry<Integer, Pair> entry : numCount.entrySet()) {
list.add(entry.getValue());
}
Collections.sort(list, (a, b) -> b.count - a.count);
int remain = arr.length, removed = 0;
for (int i = 0; i < list.size(); i++) {
if (remain > arr.length / 2) {
remain -= list.get(i).count;
removed += 1;
} else {
break;
}
}
return removed;
}
}
|
这个时间稍微快一点儿. 就是先统计每个num的freq, 做成pair. 放到list中sort一下. 然后从大到小开始踢人. 踢到满足题意为止.
时间复杂度: O(nlogn) sort + 遍历
空间复杂度: O(n) 用map和list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int minSetSize(int[] arr) {
Map<Integer, Integer> numCount = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
numCount.put(arr[i], numCount.getOrDefault(arr[i], 0) + 1);
}
PriorityQueue<Map.Entry<Integer, Integer>> q = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
for (Map.Entry<Integer, Integer> entry : numCount.entrySet()) {
q.offer(entry);
}
int remain = arr.length, removed = 0;
for (int i = 0; i < q.size(); i++) {
if (remain > arr.length / 2) {
remain -= q.poll().getValue();
removed += 1;
} else {
break;
}
}
return removed;
}
}
|
Priority Queue来去装Map的entry而不是list再sort.
时间复杂度: O(nlogn) 遍历数组获得每个num的频率(O(n)) + 把所有的entry push进queue(O(log1 + log2 + log3….数学公式是nlogn)) + poll出来(nlogn). 因此最后就是O(nlogn)
空间复杂度: O(n)
证明:
https://math.stackexchange.com/questions/482860/how-to-calc-log1-log2-log3-log4-log-n
