栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

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

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

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

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

来源于leetcode上题目

解题思路:
解决该问题的关键是找出数组中出现次数较少的整数,因此要构造一个根据整数出现次数排序的列表即ArrayList>或ArrayList ,其中Map.Entry的第一个Integer存放的是整数,第二个Integer存放的是整数出现的次数,而Integer[]中有两个数,与上同样,第一个存放的是整数,第二个存放的是整数出现的次数。通过Collection.sort()来排序,其中自定义排序方法。

代码实现:

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        HashMap new_arr = new HashMap();
//        完成数据的统计
        for (int i = 0; i < arr.length; i++) {
            int count = new_arr.getOrDefault(arr[i], 0)+1;
            new_arr.put(arr[i],count);

        }
//        排序

        ArrayList> sortArr = new ArrayList(new_arr.entrySet());
        Collections.sort(sortArr, new Comparator>() {
                    @Override
                    public int compare(Map.Entry o1, Map.Entry o2) {
                        return o1.getValue() - o2.getValue();
                    }
                }
        );
//         进行移除
        int surplus = sortArr.size();
        for (int i = 0; i < sortArr.size() && k >0; i++) {
            if(sortArr.get(i).getValue() <= k){
                surplus--;
                k -= sortArr.get(i).getValue();
            }
        }
        return surplus;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/969972.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号