class Solution {
public:
int minSetSize(vector<int>& arr) {
}
};
1338. 数组大小减半
给你一个整数数组 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 <= 105arr.length 为偶数1 <= arr[i] <= 105原站题解
golang 解法, 执行用时: 88 ms, 内存消耗: 11.9 MB, 提交时间: 2022-11-28 14:46:22
func minSetSize(arr []int) int {
//统计每个数出现的次数
countmap := make(map[int]int, 0)
maxcount := 0
for _, num := range arr {
countmap[num]++
if countmap[num] > maxcount {
maxcount = countmap[num]
}
}
//用桶排序出现次数
bucket := make([]int, maxcount+1)
for _, count := range countmap {
bucket[count]++
}
n := (len(arr) - 1) / 2
ret := 0
for count := maxcount; count > 0; count-- {
//v相同出现次数的数目,v*count相同出现次数的和
v := bucket[count]
//只有大于0才进
if v ==0 {
continue
}
if v*count < n {
//需要去掉v个数，去掉数总和为v*count
ret += v
n -= v * count
} else{
//只需要去掉n/count+1个数，同时n小于0，结束
ret += n /count + 1
return ret
}
}
return ret
}
golang 解法, 执行用时: 120 ms, 内存消耗: 19.2 MB, 提交时间: 2022-11-28 14:45:22
func minSetSize(arr []int) int {
m := map[int]int{}
for i := range arr {
m[arr[i]]++
}
d := [][]int{}
for k, v := range m {
d = append(d, []int{k, v})
}
sort.Slice(d, func(i, j int) bool {
return d[i][1] > d[j][1]
})
var r int
l := len(arr) / 2
var c int
for i := range d {
c += d[i][1]
r++
if c >= l {
return r
}
}
return 0
}
javascript 解法, 执行用时: 60 ms, 内存消耗: 53.2 MB, 提交时间: 2022-11-28 14:44:30
/**
* @param {number[]} arr
* @return {number}
*/
const minSetSize = arr => {
const LEN = arr.length;
if (LEN < 3) return 1;
const max = Math.max(...arr);
const freq = new Uint16Array(max + 1);
let maxFreq = 0;
for (const val of arr) ++freq[val] > maxFreq && (maxFreq = freq[val]);
const freqBased = new Uint32Array(maxFreq + 1);
for (const val of freq) ++freqBased[val];
let step = 0;
let sum = 0;
for (let i = maxFreq; i >= 1; --i) {
while (freqBased[i]--) {
sum += i;
++step;
if (sum >= LEN / 2) return step;
}
}
};
python3 解法, 执行用时: 104 ms, 内存消耗: 37 MB, 提交时间: 2022-11-28 14:43:28
class Solution:
def minSetSize(self, arr: List[int]) -> int:
freq = collections.Counter(arr)
cnt, ans = 0, 0
for num, occ in freq.most_common():
cnt += occ
ans += 1
if cnt * 2 >= len(arr):
break
return ans