###### tags: `Leetcode` `medium` `hash` `python`

# 1338. Reduce Array Size to The Half

## [題目連結:] https://leetcode.com/problems/reduce-array-size-to-the-half/

## 題目:
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 a size greater than half of the size of the old array.

**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.

## 解題想法:
* 題目為給一數組，求最少選多少種類的數字移除，可以使得被移除的數字數量最少為數組的一半以上。
* 用hash table:
* dic=defaultdict(int)
* key: 數字
* val: 出現次數
* 將dic 由val大小進行排序:
* nums=sorted(dic.items(),key=lambda x:x[1],reverse=True)
* type(nums)=list
* nums = [(key,val),.....]
* 計算幾組val累加會大於len(arr)//2即可

## Python:

from collections import defaultdict
class Solution(object):
    def minSetSize(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        dic=defaultdict(int)
        for val in arr:
            dic[val]+=1
        #sort by value :大到小
        nums=sorted(dic.items(),key=lambda x:x[1],reverse=True)
        # type(nums)=list -> [(key,val)]
        half=len(arr)//2
        res=0
        curSum=0
        for key,val in nums:
            res+=1
            curSum+=val
            if curSum>=half:
                return res
        return res

if __name__=='__main__':
    result=Solution()
    ans=result.minSetSize(arr = [3,3,3,3,5,5,5,2,2,7])
    print(ans) #2