Sponsored
Sponsored
This approach involves two main steps. First, count the frequency of each integer in the array. Second, use a min-heap (or priority queue) to remove the integers with the smallest frequency first. This approach ensures that we are removing the least frequent integers to reach the least number of unique integers efficiently.
Time Complexity: O(n log n) due to sorting the frequency array. Space Complexity: O(n) for storing the frequency counts.
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Solution {
6 public int LeastNumberOfUniqueInts(int[] arr, int k) {
7 var freqMap = new Dictionary<int, int>();
8 foreach (var num in arr) {
9 if (freqMap.ContainsKey(num))
10 freqMap[num]++;
11 else
12 freqMap[num] = 1;
13 }
14
15 var frequencies = freqMap.Values.ToList();
16 frequencies.Sort();
17
18 int uniqueCount = frequencies.Count;
19 foreach (var freq in frequencies) {
20 if (k >= freq) {
21 k -= freq;
22 uniqueCount--;
23 } else {
24 break;
25 }
26 }
27
28 return uniqueCount;
29 }
30
31 static void Main(string[] args) {
32 int[] arr = {4, 3, 1, 1, 3, 3, 2};
33 int k = 3;
34 Solution s = new Solution();
35 Console.WriteLine(s.LeastNumberOfUniqueInts(arr, k));
36 }
37}This C# solution uses a Dictionary to record the frequency of each element. The frequencies are sorted and used to determine the removals, effectively decrementing the count of unique integers.
This approach takes a greedy strategy to count frequencies of integers and sorts them. By progressively removing elements with smallest frequencies, it directly calculates the least number of unique integers remaining after exactly k removals.
Time Complexity: O(n log n) due to the qsort on frequencies. Space Complexity: O(n) for arrays used in frequency counting.
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
int leastNumberOfUniqueInts(vector<int>& arr, int k) {
unordered_map<int, int> count;
for (int num : arr) {
count[num]++;
}
vector<int> frequencies;
for (auto& kvp : count) {
frequencies.push_back(kvp.second);
}
sort(frequencies.begin(), frequencies.end());
int unique = frequencies.size();
for (int freq : frequencies) {
if (k >= freq) {
k -= freq;
unique--;
} else {
break;
}
}
return unique;
}
int main() {
vector<int> arr = {5, 5, 4};
int k = 1;
cout << leastNumberOfUniqueInts(arr, k) << endl;
return 0;
}The C++ solution uses an unordered_map to count integer frequencies. These frequencies are sorted, allowing for the removal starting with the smallest frequencies to minimize unique integers post deletion.