[LeetCode] 1338. 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.

Constraints:

• 2 <= arr.length <= 10^5
• arr.length is even.
• 1 <= arr[i] <= 10^5

这道题给了一个长度为偶数的数组，其中可能会有重复数字，现在说是可以移除任意个不同的数字，一次移除需要将数组中所有出现的该数字都移除。现在问最少需要移除多少个不同的数字，才能使得数组的长度不超过原来的一半。分析题目中的例子可以知道，某个数字出现的次数越多，就应该先移除他，这样数组的数字减少的最快。

那么就可以来统计数组中每个数字出现的次数，然后根据出现次数从大到小来移除，只要总移除数字大于等于数组长度的一半了，就可以了。这里使用一个 HashMap，来建立数字和其出现次数之间的映射，然后将所有的次数放入一个新的数组 cntArr 中，并将该数组由大到小进行排序。然后开始遍历，将每个数字加起来，若大于等于原数组长度的一半，就返回已遍历过的数字个数即可，参见代码如下：

解法一：

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        int n = arr.size(), half = n / 2, res = 0, cnt = 0;
        vector<int> cntArr;
        unordered_map<int, int> numCnt;
        for (int num : arr) {
            ++numCnt[num];
        }
        for (auto &a : numCnt) {
            cntArr.push_back(a.second);
        }
        sort(cntArr.rbegin(), cntArr.rend());
        for (int i = 0; i < cntArr.size(); ++i) {
            cnt += cntArr[i];
            if (cnt >= half) return i + 1;
        }
        return -1;
    }
};

再来看一种解法，这里使用了一个优先队列，将 HashMap 中统计的次数都放入优先队列中，即可以从大到小自动排好序。然后从队首开时取元素，累加，若超过数组长度的一半，则返回已经取出的元素的个数即可，参见代码如下：

解法二：

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

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1338

参考资料：

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

https://leetcode.com/problems/reduce-array-size-to-the-half/solutions/1319470/c-simple-and-clean-solution-explained-easy-to-understand/

https://leetcode.com/problems/reduce-array-size-to-the-half/solutions/1319416/c-java-python-hashmap-sort-then-counting-sort-o-n-clean-concise/

LeetCode All in One 题目讲解汇总(持续更新中...)