数组大小减半

给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。
返回 至少 能删除数组中的一半整数的整数集合的最小大小。

  • 输入：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]，新数组长度大于原数组的二分之一。

  • 输入：arr = [7,7,7,7,7,7]

  • 输出：1

  • 解释：我们只能选择集合 {7}，结果数组为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var minSetSize = function(arr) {
    // 首先需要算出每个数字在数组中出现的次数，
    // 将数组的长度按照100的比例进行划分
    let dataLength = arr.length;
    let count = {};
    arr.forEach(item=>{
        if(count[item]){
            count[item] =  ++count[item] ;
        }else {
            count[item] = 1
        }
    })
    dataLength = dataLength >> 1;  // 或者除以2取整也可以
    let vs = [...Object.values(count)].sort((a,b)=>b-a) , sum = 0,c=0,index=0;
    while(sum<dataLength){
        sum += vs[index++];
        c++
    }
    return c
};