不同整数的最少数目Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个整数数组 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

# 思路

Comparator.comparingInt

# 解法


class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        //方法1.哈希表记录每个元素出现的个数，出现个数从小到大进行移除，直到k步被用完或不够
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i : arr) map.put(i, map.getOrDefault(i, 0) + 1); //保存每个数字出现的次数
        ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet()); //转为List方便根据value排序
        list.sort(Comparator.comparingInt(Map.Entry::getValue)); //根据value从小到大排序
        while(--k >= 0){
            Integer value = list.get(0).getValue(); //取出现次数最小的value
            if(value == 1) list.remove(0); //如果出现次数为1，删除该数字
            else list.get(0).setValue(value - 1); //否则出现次数减1
        }
        return list.size(); //统计残存的数字
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 总结

分析出几种情况，然后分别对各个情况实现

#Java