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

# 1342. 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中。

```cpp
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;
    }
};
```
