X

LEETCODE 1481. Least Number of Unique Integers after K Removals 解题思路分析

题目大意:

不同整数的最少数目

给你一个整数数组 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-解题思路分析/
Categories: leetcode
kwantong: