1338 Reduce Array Size to The Half 数组巨细减半
Description:
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:
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.
Constraints:
2 <= arr.length <= 10^5
arr.length is even.
1 <= arr <= 10^5
标题形貌：
给你一个整数数组 arr。你可以从中选出一个整数聚集，并删除这些整数在数组中的每次出现。
返回 至少 能删除数组中的一半整数的整数聚集的最小巨细。
示例：
示例 1：
输入：arr = [3,3,3,3,5,5,5,2,2,7]
输出：2
表明：选择 {3,7} 使得效果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
巨细为 2 的可行聚集有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的，它的效果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。
示例 2：
输入：arr = [7,7,7,7,7,7]
输出：1
表明：我们只能选择聚集 {7}，效果数组为空。
提示：
1 <= arr.length <= 10^5
arr.length 为偶数
1 <= arr <= 10^5
思绪：
贪婪
哈希表 ➕ 优先队列
用哈希表记载每一个元素出现的次数
将出现的次数加入优先队列中
从大到小加入优先队列中的值直到凌驾数组长度的一半
时间复杂度为 O(nlgn), 空间复杂度为 O(n)
代码:
C++: |
