1338. Reduce Array Size to The Half

解题思路：题目要求是找出最少的元素，使得删除该元素之后的数组的数量顶多为原来的一半，用另外的一种解释就是删除出先次数最多的元素，使数组长度为原来的一半。

解题使用两个数据结构，

• 一个map，统计同一个元素出现的次数
• 一个priority_queue，依次找出出现次数最多的元素

时间复杂度：O(n) / 空间复杂度：O(n)

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        priority_queue<int> pq;
        unordered_map<int, int> dict;
        for(auto a : arr){
            ++dict[a];
        }
        
        for(auto d : dict){
            pq.push(d.second);
        }
        int cnt = 0, size = arr.size(), halfSize = arr.size() / 2;
        while(!pq.empty()){
            ++cnt;
            size -= pq.top();
            if(size <= halfSize){
                return cnt;
            }
            pq.pop();
        }
        return cnt;
    }
};