1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
// 1481. Least Number of Unique Integers after K Removals
#include "leetcode.h"
/*
* given an array of integers 'arr' and an integer 'k', find the least number of
* unique integers after removing exactly 'k' elements.
*/
int cmp(const void *a, const void *b) {
return *(const int *)a > *(const int *)b;
}
int findLeastNumOfUniqueInts(int *arr, int arr_size, int k) {
qsort(arr, arr_size, sizeof(int), cmp);
int idx = 0, cnt = 0, ans = 0;
int *tmp = (int *)malloc(arr_size * sizeof(int));
for (int i = 0; i < arr_size; i++) {
int j = i;
while (j < arr_size && arr[j] == arr[i])
cnt++, j++;
tmp[idx++] = cnt;
i = j - 1;
cnt = 0;
}
qsort(tmp, idx, sizeof(int), cmp);
for (int i = 0; i < idx; i++) {
ans += tmp[i];
if (ans >= k) {
ans = (ans == k) ? idx - i - 1 : idx - i;
break;
}
}
free(tmp);
return ans;
}
int main() {
int a1[] = {5, 5, 4}, a2[] = {4, 3, 1, 1, 3, 3, 2};
printf("%d\n", findLeastNumOfUniqueInts(a1, ARRAY_SIZE(a1), 1)); // expect: 1
printf("%d\n", findLeastNumOfUniqueInts(a2, ARRAY_SIZE(a2), 3)); // expect: 2
}
|