[LeetCode] 1481. Least Number of Unique Integers after K Removals

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length

不同整数的最少数目。

给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。

思路是先用hashmap记录每个不同元素的出现次数，然后按照每个元素出现次数从小到大开始删除，直到删除掉K个元素为止。如果当把某个元素全都删掉之后K < 0，则说明最后这个元素的出现次数不需要全部删除，只需要删除一部分。我这里提供两种实现，一种是最小堆；另一种是通过数组记录不同元素的出现次数，但是需要排序。两种做法都需要用到hashmap。

最小堆。用hashmap统计完数字的出现次数之后，我们把hashmap中所有的元素都放入一个最小堆，堆顶是[出现次数最少的元素，出现次数]。这样每次被pop出来的都是出现次数最少的元素。这样做我们可以尽可能多地删掉unique key，使得最后剩下的部分里unique key更少。

时间O(nlogn)

空间O(n)

Java实现

 1 class Solution {
 2     public int findLeastNumOfUniqueInts(int[] arr, int k) {
 3         HashMap<Integer, Integer> map = new HashMap<>();
 4         for (int num : arr) {
 5             map.put(num, map.getOrDefault(num, 0) + 1);
 6         }
 7 
 8         PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
 9         for (int key : map.keySet()) {
10             queue.offer(new int[] { key, map.get(key) });
11         }
12 
13         while (k > 0 && !queue.isEmpty()) {
14             int[] cur = queue.poll();
15             k -= cur[1];
16         }
17         return k < 0 ? queue.size() + 1 : queue.size();
18     }
19 }

数组排序，我们需要一个int[] count数组，长度为size，size记录的是map.size()。我们把hashmap里每个entrySet放入count数组。这样当count数组被排序之后，因为 count[i] 表示的是当前某个元素的出现次数，所以还是出现次数较小的在前。其余部分的思路跟第一种做法类似。

时间O(nlogn)

空间O(n)

Java实现

 1 class Solution {
 2     public int findLeastNumOfUniqueInts(int[] arr, int k) {
 3         HashMap<Integer, Integer> map = new HashMap<>();
 4         for (int num : arr) {
 5             map.put(num, map.getOrDefault(num, 0) + 1);
 6         }
 7 
 8         int size = map.size();
 9         int[] count = new int[size];
10         int i = 0;
11         for (int key : map.keySet()) {
12             count[i] = map.get(key);
13             i++;
14         }
15         Arrays.sort(count);
16         for (int c : count) {
17             if (k >= c) {
18                 k -= c;
19                 size--;
20             } else {
21                 break;
22             }
23         }
24         return size;
25     }
26 }

LeetCode 题目总结