题目:
Given an array arr
. You can choose a set of integers and remove all the occurrences of these integers in the array.
Return the minimum size of the set so that at least half of the integers of the array are removed.
样例:
限制:
个人思路:
先一个字典统计所有的字符出现的个数,然后按照从大到小的顺序进行排序,然后count--,当count * 2 <= len(arr)时结束,统计此时减去的数字的个数即可。
代码:
1 class Solution: 2 def minSetSize(self, arr: List[int]) -> int: 3 n = len(arr) 4 count = {} 5 for i in arr: 6 if count. __contains__(str(i)): 7 count[str(i)] +=1 8 else: 9 count[str(i)] = 1 10 count = sorted(count.items(), key=lambda x:x[1], reverse=True) 11 num = 0 12 for i in count: 13 n -= i[1] 14 num += 1 15 if n * 2 <= len(arr): 16 break 17 return num 18