# leetcode 1338. Reduce Array Size to The Half（python）

2022-01-31 23:43:13

「 This is my participation 11 The fourth of the yuegengwen challenge 20 God , Check out the activity details ：2021 One last more challenge

### describe

You are given an integer 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.

Example 1:

``````Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has size greater than half of the size of the old array.
Copy code ``````

Example 2:

``````Input: arr = [7,7,7,7,7,7]
Output: 1
Explanation: The only possible set you can choose is {7}. This will make the new array empty.
Copy code ``````

Example 3:

``````Input: arr = [1,9]
Output: 1
Copy code ``````

Example 4:

``````Input: arr = [1000,1000,3,7]
Output: 1
Copy code ``````

Example 5:

``````Input: arr = [1,2,3,4,5,6,7,8,9,10]
Output: 5
Copy code ``````

Note:

``````1 <= arr.length <= 10^5
arr.length is even.
1 <= arr[i] <= 10^5
Copy code ``````

### analysis

According to the meaning , Given an array of integers arr. You can select a set of integers and delete all those integers that have appeared in the array . The question asks us to return the size of the smallest set , To delete at least half of the integers in the array . I'm a little confused about the restrictions in the title , Has been clearly told arr.length It's even , But then he said arr.length Greater than or equal to 1 Less than or equal to 10^5 ,are you kiding ？ Is it because I didn't learn math well 1 How can it be even ？

The idea is simple ：

• Initialization result result by 0 ,L by arr Half the length , Use built-in functions Counter Yes arr Count
• Count the results according to value Descending order , Traverse all key value pairs , as long as L Greater than 0 Just result Add one , meanwhile L reduce value , Cycle this process until break , This can remove the least number and delete more than half of the integers
• Finally back to result

``````class Solution(object):
def minSetSize(self, arr):
"""
:type arr: List[int]
:rtype: int
"""
c = collections.Counter(arr)
L = len(arr)//2
result = 0
for k,v in sorted(c.items(), key=lambda x:-x):
if L>0:
result += 1
L -= v
else:
break
return result

Copy code ``````

### Running results

``````Runtime: 640 ms, faster than 52.86% of Python online submissions for Reduce Array Size to The Half.
Memory Usage: 37.3 MB, less than 35.71% of Python online submissions for Reduce Array Size to The Half.
Copy code ``````