diff options
Diffstat (limited to 'least_num_unique_int.c')
-rw-r--r-- | least_num_unique_int.c | 41 |
1 files changed, 41 insertions, 0 deletions
diff --git a/least_num_unique_int.c b/least_num_unique_int.c new file mode 100644 index 0000000..4e4b4f6 --- /dev/null +++ b/least_num_unique_int.c @@ -0,0 +1,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 +} |