友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
1481. 不同整数的最少数目
给你一个整数数组 arr 和一个整数 k。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。
示例 1：
输入：arr = [5,5,4], k = 1 输出：1 解释：移除 1 个 4 ，数组中只剩下 5 一种整数。
示例 2：
输入：arr = [4,3,1,1,3,3,2], k = 3 输出：2 解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。
提示：
-
1 <= arr.length <= 10^5 -
1 <= arr[i] <= 10^9 -
0 <= k <= arr.length
思路分析
先统计每个数字出现的次数，再根据出现次数，升序排列，从前向后删除数字即可。
可以用优先队列，也可以排序。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-09-03 21:12:52
*/
public int findLeastNumOfUniqueInts(int[] arr, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int i : arr) {
cnt.put(i, cnt.getOrDefault(i, 0) + 1);
}
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator
.comparingInt(a -> cnt.getOrDefault(a, 0)));
for (Integer n : cnt.keySet()) {
pq.offer(n);
}
while (k > 0) {
Integer n = pq.poll();
Integer c = cnt.get(n);
if (k >= c) {
cnt.remove(n);
k -= c;
} else {
cnt.put(n, c - k);
k = 0;
}
}
return cnt.keySet().size();
}