题目
- 不同整数的最少数目
给你一个整数数组 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
提交记录
这种方法效率比较低。
代码
import java.util.Map;
class Solution {public int findLeastNumOfUniqueInts(int[] arr, int k) {// 数组转Map，key（数组元素），value（元素出现的次数）Map<Integer,Integer> map = new HashMap<Integer, Integer>();for(int i=0; i<arr.length; i++){if(map.containsKey(arr[i])){int val = map.get(arr[i]);map.put(arr[i],val+1);}else{map.put(arr[i],1);}}// 按照value值（数组中元素重复出现的次数）从小到大排序HashMap<Integer, Integer> sortMap = new LinkedHashMap<Integer, Integer>();List<Map.Entry<Integer, Integer>> mapList = map.entrySet().stream().sorted((p1,p2)->p1.getValue().compareTo(p2.getValue())).collect(Collectors.toList());//遍历集合，将排好序的键值对Entry<K,V>放入新的map并返回。mapList.forEach(ele->sortMap.put(ele.getKey(), ele.getValue()));// map转listList<Integer> list = new ArrayList<>();for(Map.Entry<Integer,Integer> entry:sortMap.entrySet()){for(int i=0;i<entry.getValue();i++){list.add(entry.getKey());}};// 删除排序后的list前k个元素for (int y = 0; y < k; y++) {list.remove(0);}// 去重TreeSet<Integer> set = new TreeSet<>(list);return set.size();}
}
