Problem: 1338. 数组大小减半 贪心 模拟 法 简单易懂

Problem: 1338. 数组大小减半

思路

因为要选择最小的整数集合，这里用Counter容器来统计下所有各种数字的大小，然后按照值来排序，设置target来表示要到达什么位置，这里最好不要用整除，防止要计算的大于arr，但是len(arr)是奇数，这里total表示删除到这个位置已经删除了多少数字，如果大于等于target就是可以break，然后ans记录当前已经删了多少，就是贪心从最多的开始删除。

复杂度

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
def minSetSize(self, arr: List[int]) -> int:
count=Counter(arr)

    fre=sorted(count.values(),reverse=True)

    target=len(arr)/2
    total=0
    ans=0
    for i in fre:
        total+=i
        ans+=1
        if total>=target:
            break
    return ans