企业官网建设流程全解析

1. 题目解析与核心思路

1481题"不同整数的最少数目"是LeetCode上一道中等难度的贪心算法练习题。题目要求：给定一个整数数组arr和一个整数k，我们需要从数组中移除恰好k个元素，使得剩下的数组中不同整数的数量尽可能少。

举个具体例子： 输入：arr = [5,5,4], k = 1 输出：1 解释：移除单个4后，剩下[5,5]只有1种数字

1.1 问题本质分析

这道题的核心在于理解"不同整数的最少数目"这个优化目标。我们需要通过移除k个元素，使得剩余数组中unique元素的数量最小化。关键在于：

1. 统计每个数字的出现频率
2. 优先移除出现次数少的数字（因为移除它们可以用最少的操作减少unique count）
3. 当移除机会(k)用完时，剩下的unique count就是答案

1.2 贪心算法适用性

这个问题非常适合用贪心算法解决，因为：

• 局部最优选择（每次移除出现最少的数字）能导致全局最优解
• 不需要考虑之前的选择对后续的影响
• 问题具有最优子结构性质

2. 详细解题步骤

2.1 频率统计与排序

首先我们需要统计每个数字出现的频率，然后按照频率升序排列：

from collections import Counter def findLeastNumOfUniqueInts(arr, k): freq = Counter(arr) sorted_freq = sorted(freq.items(), key=lambda 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

这个循环中，我们：

1. 初始化unique_count为所有不同数字的数量
2. 遍历排序后的频率列表
3. 如果当前数字的全部出现次数都可以被移除(k >= count)，就减少k和unique_count
4. 如果不能完全移除，就停止（因为剩下的数字都需要保留至少一个）

2.3 完整代码实现

将上述两部分组合起来就是完整解法：

from collections import Counter def findLeastNumOfUniqueInts(arr, k): freq = Counter(arr) sorted_freq = sorted(freq.items(), key=lambda 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_count

3. 复杂度分析与优化

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 可能的优化方向

1. 当k=0时可以直接返回unique count
2. 当k>=n时可以直接返回0
3. 使用堆数据结构可以避免完全排序

优化后的版本：

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 常见边界情况

1. k=0：不应该移除任何元素
   • 输入：[1,2,3], k=0 → 输出：3
2. k=数组长度：可以移除所有元素
   • 输入：[1,1,2,2], k=4 → 输出：0
3. 所有元素相同：
   • 输入：[7,7,7,7], k=2 → 输出：1
4. 需要部分移除某个数字：
   • 输入：[4,3,1,1,3,3,2], k=3 → 输出：2（移除两个1和一个2）

4.2 测试用例设计技巧

设计测试用例时应考虑：

1. 常规情况（混合频率）
2. 极端情况（全相同/全不同）
3. k的边界值（0，数组长度）
4. 部分移除的情况
5. 大数测试（验证效率）

5. 同类题目与扩展思考

5.1 LeetCode类似题目

1. 347. 前K个高频元素（同样需要频率统计）
2. 451. 根据字符出现频率排序
3. 692. 前K个高频单词
4. 1054. 距离相等的条形码（频率分配问题）

5.2 实际应用场景

这类频率统计+贪心选择的问题在实际中有很多应用：

1. 数据压缩（移除低频数据）
2. 缓存淘汰策略（LRU/LFU）
3. 资源分配问题
4. 特征选择（机器学习中移除低频特征）

5.3 算法选择思考

为什么贪心算法在这里有效？因为：

1. 移除低频数字能最大化减少unique count
2. 每个选择不影响后续选择的可行性
3. 不需要回溯或考虑所有可能性

对于贪心算法问题，关键是证明贪心选择的正确性。在这个问题中，假设有一个最优解移除的不是当前最低频的数字，我们总能通过交换移除顺序得到一个不差于它的解。