【灵神题单·贪心】1481. 不同整数的最少数目 | 频率排序贪心 | Java

题目链接1481. 不同整数的最少数目 所属题单灵茶山艾府 · 贪心算法题单 — §1.1 从最小/最大开始贪心️ 难度Medium | 难度分1284 标签贪心、哈希表、排序 题目描述给你一个整数数组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 arr.length 10^51 arr[i] 10^90 k arr.length 思路分析要让剩余的不同整数种类最少→ 尽可能多消灭整数种类→ 优先干掉出现次数最少的想象你在整理书架要丢掉 k 本书让品种最少。肯定先丢只有 1 本的那个品种再丢只有 2 本的…… 这样最快清掉一个品种 算法步骤统计频率用 HashMap 记录每个数出现几次频率排序从小到大排贪心删除从频率最小的开始扣减 kk 够就整个消灭✅ 代码实现JavaclassSolution{publicintfindLeastNumOfUniqueInts(int[]arr,intk){MapInteger,IntegerfreqnewHashMap();for(intx:arr){freq.merge(x,1,Integer::sum);}ListIntegercountsnewArrayList(freq.values());Collections.sort(counts);intremoved0;for(inti0;icounts.size();i){if(kcounts.get(i)){k-counts.get(i);removed;}else{break;}}returncounts.size()-removed;}} 复杂度分析复杂度说明⏱️ 时间O(n log n)频率排序 空间O(n)哈希表 参考灵茶山艾府 · 贪心算法题单 和 3545 是镜像题——那道是删字符使种类 ≤ k这道是删 k 个使种类最少。核心一样频率排序 从最少的开始动手。