1338 数组大小减半

题目链接

1338. 数组大小减半

分析

贪心

用哈希表统计每个数出现的次数，按降序排序

从大到小求和，超过数组长度一半时即得出答案

代码实现

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        int ans = 0, n = arr.size() >> 1;
        vector<int> v;
        unordered_map<int, int> um;

        for(int& i : arr)
            um[i]++;

        for(auto& [_, i] : um)
            v.emplace_back(i);
  
        ranges::sort(v, greater());

        for(int i = 0; i < n; ++i) // 循环上界写着玩的，可以留空
        {
            if(v[i] >= n)
            {
                ans = i + 1;
                break;
            }
            v[i + 1] += v[i];
        }

        return ans;
    }
};
```cpp
class Solution {
public:
    int minSetSize(vector<int>& arr) {
        int ans = 0, n = arr.size() >> 1;
        vector<int> v;
        unordered_map<int, int> um;

        for(int& i : arr)
            um[i]++;

        for(auto& [_, i] : um)
            v.emplace_back(i);
  
        ranges::sort(v, greater());

        for(int i = 0; i < n; ++i) // 循环上界写着玩的，可以留空
        {
            if(v[i] >= n)
            {
                ans = i + 1;
                break;
            }
            v[i + 1] += v[i];
        }

        return ans;
    }
};

### 复杂度分析

- 时间复杂度：$O(n \log n)$，主要为排序耗时
- 空间复杂度：$O(n)$