C++에서 배열 크기를 절반으로 줄이기

배열 arr이 있다고 가정합니다. 정수 집합을 선택하고 배열에서 이러한 정수의 모든 항목을 제거할 수 있습니다. 배열의 정수 중 적어도 절반이 제거되도록 집합의 최소 크기를 찾아야 합니다. 예를 들어, arr =[3,3,3,3,5,5,5,2,2,7]이면 출력은 2가 됩니다. 이는 {3,7}을 선택하면 크기가 5인 새 배열 [5,5,5,2,2]입니다(이전 배열 크기의 절반과 같음). 크기 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
- 그 값을 temp에 삽입
임시 배열 정렬
범위 0에서 온도 크기까지의 I에 대해
- sz <=n / 2이면 루프에서 분리
- ret 1 증가
- temp[i]에 의해 sz 감소
리턴 렛

예시(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]