数组大小减半Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。
返回 至少 能删除数组中的一半整数的整数集合的最小大小。
示例 1：
输入：arr = [3,3,3,3,5,5,5,2,2,7]
输出：2
解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。
示例 2：
输入：arr = [7,7,7,7,7,7]
输出：1
解释：我们只能选择集合 {7}，结果数组为空。
提示：
- 1 <= arr.length <= 105
- arr.length 为偶数
- 1 <= arr[i] <= 105
# 思路
Arrays.sort(note);
# 解法
class Solution {
public int minSetSize(int[] arr) {
int[] note = new int[100001];
for (int i : arr) {
note[i]++;
}
Arrays.sort(note);
int r = 0, s = 0, len = arr.length / 2;
for (int i = note.length - 1; i >= 0; i--) {
r++;
s += note[i];
if (s >= len) {
break;
}
}
return r;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 总结
- 分析出几种情况，然后分别对各个情况实现
