1. 题目解析与核心思路1481题不同整数的最少数目是LeetCode上一道中等难度的贪心算法练习题。题目要求给定一个整数数组arr和一个整数k我们需要从数组中移除恰好k个元素使得剩下的数组中不同整数的数量尽可能少。举个具体例子 输入arr [5,5,4], k 1 输出1 解释移除单个4后剩下[5,5]只有1种数字1.1 问题本质分析这道题的核心在于理解不同整数的最少数目这个优化目标。我们需要通过移除k个元素使得剩余数组中unique元素的数量最小化。关键在于统计每个数字的出现频率优先移除出现次数少的数字因为移除它们可以用最少的操作减少unique count当移除机会(k)用完时剩下的unique count就是答案1.2 贪心算法适用性这个问题非常适合用贪心算法解决因为局部最优选择每次移除出现最少的数字能导致全局最优解不需要考虑之前的选择对后续的影响问题具有最优子结构性质2. 详细解题步骤2.1 频率统计与排序首先我们需要统计每个数字出现的频率然后按照频率升序排列from collections import Counter def findLeastNumOfUniqueInts(arr, k): freq Counter(arr) sorted_freq sorted(freq.items(), keylambda x: x[1])这里使用Python的Counter来统计频率然后通过sorted函数按值排序。时间复杂度是O(n log n)主要来自排序操作。2.2 贪心移除过程接下来我们按照频率从低到高的顺序移除数字unique_count len(sorted_freq) for num, count in sorted_freq: if k count: k - count unique_count - 1 else: break return unique_count这个循环中我们初始化unique_count为所有不同数字的数量遍历排序后的频率列表如果当前数字的全部出现次数都可以被移除(k count)就减少k和unique_count如果不能完全移除就停止因为剩下的数字都需要保留至少一个2.3 完整代码实现将上述两部分组合起来就是完整解法from collections import Counter def findLeastNumOfUniqueInts(arr, k): freq Counter(arr) sorted_freq sorted(freq.items(), keylambda x: x[1]) unique_count len(sorted_freq) for num, count in sorted_freq: if k count: k - count unique_count - 1 else: break return unique_count3. 复杂度分析与优化3.1 时间复杂度统计频率O(n)排序频率O(m log m)其中m是unique元素的数量贪心移除O(m) 总体时间复杂度是O(n m log m)在大多数情况下可以视为O(n log n)3.2 空间复杂度频率字典O(m)排序后的列表O(m) 总体空间复杂度是O(m)3.3 可能的优化方向当k0时可以直接返回unique count当kn时可以直接返回0使用堆数据结构可以避免完全排序优化后的版本from collections import Counter import heapq def findLeastNumOfUniqueInts(arr, k): if k 0: return len(set(arr)) if k len(arr): return 0 freq Counter(arr) heap [] for num, count in freq.items(): heapq.heappush(heap, (count, num)) while k 0 and heap: count, num heapq.heappop(heap) if k count: k - count else: heapq.heappush(heap, (count - k, num)) k 0 return len(heap)这个版本使用最小堆来获取当前出现次数最少的数字在某些情况下可能更高效。4. 边界条件与测试用例4.1 常见边界情况k0不应该移除任何元素输入[1,2,3], k0 → 输出3k数组长度可以移除所有元素输入[1,1,2,2], k4 → 输出0所有元素相同输入[7,7,7,7], k2 → 输出1需要部分移除某个数字输入[4,3,1,1,3,3,2], k3 → 输出2移除两个1和一个24.2 测试用例设计技巧设计测试用例时应考虑常规情况混合频率极端情况全相同/全不同k的边界值0数组长度部分移除的情况大数测试验证效率5. 同类题目与扩展思考5.1 LeetCode类似题目前K个高频元素同样需要频率统计根据字符出现频率排序前K个高频单词距离相等的条形码频率分配问题5.2 实际应用场景这类频率统计贪心选择的问题在实际中有很多应用数据压缩移除低频数据缓存淘汰策略LRU/LFU资源分配问题特征选择机器学习中移除低频特征5.3 算法选择思考为什么贪心算法在这里有效因为移除低频数字能最大化减少unique count每个选择不影响后续选择的可行性不需要回溯或考虑所有可能性对于贪心算法问题关键是证明贪心选择的正确性。在这个问题中假设有一个最优解移除的不是当前最低频的数字我们总能通过交换移除顺序得到一个不差于它的解。