1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
# 1338. Reduce Array Size to The Half
from collections import Counter
"""
you are given an integer array 'arr'. you can choose a set of integers and
remove all the occurences of these integers in the array. return the minimum
size of the set so that at least half of the integers in the array are
removed.
"""
class Solution(object):
def minSetSize(self, arr):
"""
:type arr: List[int]
:rtype: int
"""
cnt = Counter(arr)
freq = list(cnt.values())
freq.sort()
ans, removed, half = 0, 0, len(arr) // 2
while removed < half:
ans += 1
removed += freq.pop()
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.minSetSize(arr=[3, 3, 3, 3, 5, 5, 5, 2, 2, 7]))
print(obj.minSetSize(arr=[7, 7, 7, 7, 7, 7]))
|