関小君刷题记

题目大意：

不同整数的最少数目

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1481

解题思路分析：

1. 遍历一遍数组，记录下每种数字的个数。
2. 将每种元素的个数存入数组count[]，并对数组count[]进行排序。（count数组的大小即是所有数字的种类数。）
3. 移除k个元素后，使得数组中数字种类最少的方式即是，删除那些个数少的，留下个数多的元素。由于留下的元素个数相对较多，因此种类也就相对变少。
4. 从小到大循环count数组，用k减去当前的个数，如果k仍大于0，代表删除完当前元素后，还需删除其他元素，继续循环。如果k等于0，代表删除完当前元素后，刚好总共删除了k个元素，那么当前下标之后的元素个数和即是剩余元素种类。如果k小于0，代表当前元素个数多于k，也就是说删除完k个元素后，当前元素还有剩余，因此当前下标到数组结尾的个数为剩余元素种类。

实现代码：

public int findLeastNumOfUniqueInts(int[] arr, int k) {
    Map<Integer,Integer> map = new HashMap<>();
    for(int num : arr){ // 统计每种数字的个数
        int count=map.getOrDefault(num,0);
        map.put(num,count+1);
    }
    int[] count=new int[map.size()]; // 将所有个数存入数组
    int index=0;
    for(int key : map.keySet()){
        count[index]=map.get(key);
        index++;
    }
    Arrays.sort(count); // 对数组进行排序
    for(int i=0;i<count.length;i++){
        k-=count[i]; // 减去当前元素的个数
        // 当前元素全部被删除，之后的下标个数为剩余元素个数
        if(k==0) return count.length-i-1;
        // 当前元素还有剩余，当前下标到结尾的下标个数为剩余元素个数
        else if(k<0) return count.length-i;
    }
    return 0;
}

本题解法执行时间为71ms。

Runtime: 71 ms, faster than 74.18% of Java online submissions for Least Number of Unique Integers after K Removals.

Memory Usage: 92.1 MB, less than 50.00% of Java online submissions for Least Number of Unique Integers after K Removals.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1481-least-number-of-unique-integers-after-k-removals-解题思路分析/