Sponsored
Sponsored
This approach involves sorting the elements of the array based on their frequency. We start by counting the frequency of each element. Next, we create a list of these frequencies sorted in decreasing order. By selecting the most frequent elements first, we remove them from the array until at least half of the array size is removed.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing frequencies.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return *(int*)b - *(int*)a;
6}
7
8int minSetSize(int* arr, int arrSize) {
9 int frequency[100001] = {0};
10 for (int i = 0; i < arrSize; i++) {
11 frequency[arr[i]]++;
12 }
13
14 int freqCount[100001] = {0};
15 int freqSize = 0;
16 for (int i = 0; i < 100001; i++) {
17 if (frequency[i] > 0) {
18 freqCount[freqSize++] = frequency[i];
19 }
20 }
21
22 qsort(freqCount, freqSize, sizeof(int), compare);
23
24 int sum = 0, setSize = 0;
25 for (int i = 0; i < freqSize; i++) {
26 sum += freqCount[i];
27 setSize++;
28 if (sum >= arrSize / 2) {
29 return setSize;
30 }
31 }
32 return setSize;
33}
34
35int main() {
36 int arr[] = {3,3,3,3,5,5,5,2,2,7};
37 int arrSize = sizeof(arr)/sizeof(arr[0]);
38 printf("%d\n", minSetSize(arr, arrSize));
39 return 0;
40}
41The code defines a function minSetSize that calculates the minimum set size required to remove at least half of the integers in the array. It uses an array to count the frequency of each element, sorts this frequency array, and removes elements starting with the most frequent to fulfill the condition. The function returns the size of the set needed.
This approach utilizes bucket sort, where frequencies are counted and used as indices in a bucket array to represent how many numbers occur with identical frequency. This helps in efficiently choosing elements to remove, optimizing beyond traditional sorting by directly accessing through indices.
Time Complexity: O(n) because of bucket sorting.
Space Complexity: O(n) due to auxiliary arrays.
1#include <vector>
#include <unordered_map>
using namespace std;
int minSetSize(vector<int>& arr) {
unordered_map<int, int> count;
for (int num : arr) count[num]++;
vector<int> bucket(arr.size() + 1, 0);
for (auto& pair : count) {
bucket[pair.second]++;
}
int halfSize = arr.size() / 2, removed = 0, setSize = 0;
for (int i = arr.size(); i > 0; i--) {
while (bucket[i] > 0) {
removed += i;
setSize++;
bucket[i]--;
if (removed >= halfSize) return setSize;
}
}
return setSize;
}
int main() {
vector<int> arr = {3,3,3,3,5,5,5,2,2,7};
cout << minSetSize(arr) << endl;
return 0;
}
The C++ version integrates a bucket sort approach for frequency counting, where the bucket array utilizes indices to represent frequencies of numbers. This results in an optimal removal process by iterating from frequencies with larger indices to minimize the size of the set needed to meet the problem conditions.