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.
1#include <iostream>
2#include <unordered_map>
3#include <vector>
4#include <algorithm>
5using namespace std;
6
7int leastNumberOfUniqueInts(vector<int>& arr, int k) {
8 unordered_map<int, int> freqMap;
9 for (int num : arr) {
10 freqMap[num]++;
11 }
12
13 vector<int> freqValues;
14 for (auto entry : freqMap) {
15 freqValues.push_back(entry.second);
16 }
17
18 sort(freqValues.begin(), freqValues.end());
19
20 int uniqueCount = freqValues.size();
21 for (int freq : freqValues) {
22 if (k >= freq) {
23 k -= freq;
24 uniqueCount--;
25 } else {
26 break;
27 }
28 }
29
30 return uniqueCount;
31}
32
33int main() {
34 vector<int> arr = {4, 3, 1, 1, 3, 3, 2};
35 int k = 3;
36 cout << leastNumberOfUniqueInts(arr, k) << endl;
37 return 0;
38}In this C++ solution, we use an unordered_map to count the frequency of each integer. We then sort these frequencies and remove elements starting from the smallest frequency. This enables us to efficiently reach the least possible number 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.
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int LeastNumberOfUniqueInts(int[] arr, int k) {
Dictionary<int, int> count = new Dictionary<int, int>();
foreach (int num in arr) {
if (count.ContainsKey(num))
count[num]++;
else
count[num] = 1;
}
List<int> frequencies = count.Values.ToList();
frequencies.Sort();
int uniqueCount = frequencies.Count;
foreach (int f in frequencies) {
if (k >= f) {
k -= f;
uniqueCount--;
} else {
break;
}
}
return uniqueCount;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.LeastNumberOfUniqueInts(new int[] {5, 5, 4}, 1));
}
}This C# code uses a dictionary to determine the frequency of each element. Frequencies are sorted, allowing for strategic removal to reduce the count of unique integers remaining.