C++ 中将数组大小减半

假设我们有一个数组 arr。我们可以选择一组整数并删除数组中这些整数的所有出现。我们必须找到集合的最小大小，以便删除数组中至少一半的整数。例如，如果 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]，其大小大于旧数组大小的一半。

为了解决这个问题，我们将遵循以下步骤：

• 定义一个映射 m，n := arr 的大小，将 arr 中存在的每个元素的频率存储到映射 m 中

• 定义一个名为 temp 的数组，sz := n，以及 ret := 0

• 对于 m 中的每个键值对 it

  • 将 it 的值插入到 temp 中

• 对 temp 数组进行排序

• 对于 I 从 0 到 temp 的大小

  • 如果 sz <= n / 2，则退出循环

  • 将 ret 加 1

  • 将 sz 减去 temp[i]

• 返回 ret

示例 (C++)

让我们看看下面的实现，以便更好地理解：

 在线演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minSetSize(vector<int>& arr) {
      unordered_map <int, int> m;
      int n = arr.size();
      for(int i = 0; i < n; i++){
         m[arr[i]]++;
      }
      vector <int> temp;
      unordered_map <int, int> :: iterator it = m.begin();
      int sz = n;
      int ret = 0;
      while(it != m.end()){
         temp.push_back(it->second);
         it++;
      }
      sort(temp.rbegin(), temp.rend());
      for(int i = 0; i < temp.size(); i++){
         if(sz <= n / 2)break;
         ret++;
         sz -= temp[i];
      }
      return ret;
   }
};
main(){
   vector<int> v = {3,3,3,3,5,5,5,2,2,7};
   Solution ob;
   cout << (ob.minSetSize(v));
}

输入

[3,3,3,3,5,5,5,2,2,7]

输出

2

Arnab Chakraborty

更新于: 2020-04-29

1K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

立即开始