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 <iostream>
2#include <vector>
3#include <unordered_map>
4#include <algorithm>
5
6using namespace std;
7
8int minSetSize(vector<int>& arr) {
9 unordered_map<int, int> frequency;
10 for (int num : arr) {
11 frequency[num]++;
12 }
13
14 vector<int> freqValues;
15 for (auto& pair : frequency) {
16 freqValues.push_back(pair.second);
17 }
18
19 sort(freqValues.rbegin(), freqValues.rend());
20
21 int removed = 0, setSize = 0;
22 for (int freq : freqValues) {
23 removed += freq;
24 setSize++;
25 if (removed >= arr.size() / 2) {
26 break;
27 }
28 }
29 return setSize;
30}
31
32int main() {
33 vector<int> arr = {3,3,3,3,5,5,5,2,2,7};
34 cout << minSetSize(arr) << endl;
35 return 0;
36}
37The function minSetSize uses a hash map to count the frequency of each element in the array. It then sorts these frequencies in descending order and iteratively removes the most frequent elements, maintaining a count of how many numbers have been removed until at least half of the original array is eliminated.
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
This C code implements a bucket-based frequency count. It populates a bucket array where the index represents frequency and the value represents how many numbers have that frequency. By accessing these buckets from highest to lowest, we efficiently calculate the number of elements we need to remove from the array to reach at least half its size.