LeetCode 1338题解：贪心算法与哈希表应用

1. 题目解析与核心思路LeetCode 1338题Reduce Array Size to The Half要求我们找到从数组中移除最少数量的元素使得剩余元素的数量不超过原数组大小的一半。这道题在周赛和日常练习中出现频率较高属于贪心算法与哈希表结合的典型应用题。1.1 问题重述给定一个整数数组arr我们可以从中选择一个整数集合并删除数组中所有出现在该集合中的元素。要求返回能满足删除后数组大小最多为原数组一半的最小集合大小。示例 输入arr [3,3,3,3,5,5,5,2,2,7] 输出2 解释选择{3,5}这两个元素删除后数组将变为[2,2,7]长度为3 ≤ 5原长度10的一半1.2 解题关键点这道题的核心在于理解两个关键要素删除操作的效果删除某个元素会移除数组中所有该元素的出现优化目标用最少的删除操作达到数组长度减半通过分析可以得出我们应该优先删除出现频率最高的元素因为这样可以用最少的删除操作移除最多的数组元素。这正是贪心算法的典型应用场景。2. 算法设计与实现2.1 基础解法哈希表排序最直观的解法分为三个步骤统计每个元素的出现频率按频率从高到低排序从高频元素开始删除直到满足条件int minSetSize(vectorint arr) { unordered_mapint, int freq; for (int num : arr) freq[num]; vectorint frequencies; for (auto [num, count] : freq) { frequencies.push_back(count); } sort(frequencies.begin(), frequencies.end(), greaterint()); int total 0; int res 0; for (int count : frequencies) { total count; res; if (total arr.size() / 2) break; } return res; }2.2 优化解法计数排序当数组元素范围较大但不同元素数量不多时可以使用计数排序进一步优化int minSetSize(vectorint arr) { unordered_mapint, int freq; for (int num : arr) freq[num]; int max_freq 0; for (auto [num, count] : freq) { max_freq max(max_freq, count); } vectorint count(max_freq 1, 0); for (auto [num, cnt] : freq) { count[cnt]; } int res 0; int removed 0; for (int i max_freq; i 1; i--) { while (count[i] 0) { removed i; res; count[i]--; if (removed arr.size() / 2) return res; } } return res; }2.3 复杂度分析基础解法时间复杂度O(n log n)主要来自排序操作空间复杂度O(n)存储频率和排序结果优化解法时间复杂度O(n)避免了排序操作空间复杂度O(n)需要存储频率计数3. 常见问题与调试技巧3.1 边界条件处理在实际编码中有几个边界条件需要特别注意数组长度为1时直接返回1当所有元素都相同时返回1当数组长度为偶数时严格减半奇数时向下取整3.2 调试技巧遇到问题时可以尝试以下调试方法打印频率统计结果确认是否正确检查排序后的频率数组是否按降序排列在累加过程中打印中间结果确认终止条件是否正确3.3 性能优化点对于大规模数据可以考虑以下优化使用reserve预分配哈希表空间对于特定语言选择更高效的数据结构并行化频率统计过程对于超大规模数据4. 同类问题扩展掌握这道题的解法后可以尝试解决以下类似问题LeetCode 347. Top K Frequent ElementsLeetCode 692. Top K Frequent WordsLeetCode 451. Sort Characters By Frequency这些题目都涉及到频率统计和优先处理高频元素的思路是巩固这一解题模式的良好练习。5. 实际应用场景这类频率统计和优化删除的问题在实际开发中有多种应用缓存淘汰策略优先移除访问频率最低的数据数据压缩识别并移除冗余的高频数据日志分析找出最常出现的错误类型资源清理确定占用空间最大的文件类型进行优先清理理解这类算法有助于我们在实际工程问题中做出更优的决策。