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 <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int leastNumberOfUniqueInts(int* arr, int arrSize, int k) {
9 int frequency[100001] = {0};
10 for (int i = 0; i < arrSize; ++i) {
11 frequency[arr[i]]++;
12 }
13
14 int frequencies[100001] = {0};
15 int index = 0;
16 for (int i = 0; i < 100001; ++i) {
17 if (frequency[i] > 0) {
18 frequencies[index++] = frequency[i];
19 }
20 }
21
22 qsort(frequencies, index, sizeof(int), compare);
23
24 int uniqueCount = index;
25 for (int i = 0; i < index && k > 0; ++i) {
26 if (frequencies[i] <= k) {
27 k -= frequencies[i];
28 uniqueCount--;
29 } else {
30 break;
31 }
32 }
33
34 return uniqueCount;
35}
36
37int main() {
38 int arr[] = {4, 3, 1, 1, 3, 3, 2};
39 int k = 3;
40 printf("%d\n", leastNumberOfUniqueInts(arr, sizeof(arr) / sizeof(arr[0]), k));
41 return 0;
42}This C program implements the approach by utilizing an array to keep the frequency of each integer. It then collects these frequencies into another array which is sorted to allow removal of the lowest frequencies first. A loop continues removing these and reducing the count of unique integers. A direct index is maintained to access frequencies in order.
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.
1
The JavaScript approach uses a Map for frequency counting, sorts the frequencies, and removes the least frequent elements first, effectively reducing unique integer count.