1342. Reduce Array Size to The Half

https://leetcode.com/problems/reduce-array-size-to-the-half/

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.

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.

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.

Example 3:

Input: arr = [1,9]
Output: 1

Example 4:

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

Example 5:

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

Constraints:

• 1 <= arr.length <= 10^5

• arr.length is even.

• 1 <= arr[i] <= 10^5

选定元素值可去除数组中所有等值的元素，问最少可选几个元素能让数组长度降到一半或以下。统计元素出现的频率，从频率最高开始删直到满足条件。因此把频率看作bucket，把对应频率的元素个数放到bucket中。

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        const int N = arr.size();
        unordered_map<int, int> freq;
        for (const auto &a : arr) ++freq[a];
        vector<int> nums(N + 1, 0);
        for (const auto &p : freq) ++nums[p.second];
        int res = 0;
        for (int i = N, cnt = 0; i >= 0; --i) {
            if (cnt + nums[i] * i < N / 2) {
                res += nums[i];
                cnt += nums[i] * i;
            } else {
                res += (N / 2 - cnt) / i;
                if ((N / 2 - cnt) % i != 0) ++res; 
                break;
            }
        }
        return res;
    }
};