LeetCode 575 分糖果Distribute Candies题解set 去重 min 取值的贪心推导【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文是 leetcode 题解仓库中 problems/575.distribute-candies.md 的完整讲解以 LeetCode 第 575 题“分糖果Distribute Candies”为对象从题目约束出发推导出“妹妹能获得的最大糖果种类数 min(糖果种类数, n/2)”这一核心结论并给出 JS 与 Python 两种可运行实现。读完本文你将掌握这一类“均值分配 种类上限”问题的分析套路以及Set去重与位运算取半等实现细节。题目信息题目编号575中文题解problems/575.distribute-candies.md英文题解problems/575.distribute-candies.en.md难度定位简单Easy收录于仓库的 collections/easy.md 以及 SUMMARY.md 的目录中出现公司阿里、字节据原题解文档记录题目描述给定一个偶数长度的数组其中不同的数字代表着不同种类的糖果每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。示例 1输入: candies [1,1,2,2,3,3] 输出: 3 解析: 一共有三种种类的糖果每一种都有两个。 最优分配方案妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。示例 2输入: candies [1,1,2,3] 输出: 2 解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1]妹妹有两种不同的糖果弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。注意数组的长度为[2, 10,000]并且确定为偶数数组中数字的大小在范围[-100,000, 100,000]内。前置知识数组基础thinkings/basic-data-structure.md理解数组遍历、去重与长度统计是本解法的基础。本题核心操作Set去重本质上就是对数组元素的一次完整扫描。思路分析为什么答案是min(种类数, n/2)设数组长度为n由于糖果总数为偶数且必须平均分配妹妹最多只能拿到n / 2颗糖果。那么妹妹能获得的最大种类数取决于什么只需要分两种情况讨论糖果种类数大于n / 2此时即使妹妹每颗糖都拿不同种类她也只有n / 2颗糖因此最多只能拿到n / 2种糖果种类数小于n / 2糖果种类本身就那么多妹妹把所有种类各拿一颗即可拿到全部种类数。综合两种情况妹妹能够获得的糖果种类的制约因素其实是糖果种类数最终答案就是答案 min(糖果种类数, n / 2)其中“糖果种类数”即数组中不同数字的个数可以直接用去重集合的大小来表示。下图直观对比了“种类多但每种数量少”与“种类少但数量多”两种场景的差异该图存放于仓库 assets/problems/575.distribute-candies.png仓库中还保留了该思路的 drawio 绘图源文件 assets/drawio/575.distribute-candies.drawio便于对推导过程进行二次编辑与复现。关键点解析这是一道逻辑题目只要把“妹妹最多拿n/2颗”与“种类数可能不足n/2”这两层约束想清楚代码就是自然而然的——不需要排序、不需要双指针、不需要复杂的贪心策略一次遍历统计去重即可。题目已经保证n为偶数因此n / 2一定是整数不必担心小数取整问题不过使用位运算n 1仍然是最稳妥、最高效的取半写法。代码实现本题解支持 JS 与 Python 两种语言。JavaScript 实现/* * lc appleetcode id575 langjavascript * * [575] Distribute Candies */ /** * param {number[]} candies * return {number} */ var distributeCandies function (candies) { const count new Set(candies); // Set 自动去重size 即为糖果种类数 return Math.min(count.size, candies.length 1); // 取种类数与 n/2 的较小值 };说明new Set(candies)会对数组做一次去重count.size得到的就是糖果种类数candies.length 1等价于candies.length / 2的向下取整由于题目保证长度为偶数两者结果一致Math.min(count.size, candies.length 1)正是上文推导出的最终公式。Python 实现class Solution: def distributeCandies(self, candies: List[int]) - int: # len(set(candies)) 统计糖果种类数len(candies) 1 为妹妹可获得的糖果数量上限 return min(len(set(candies)), len(candies) 1)说明set(candies)完成去重len(set(candies))为种类数len(candies) 1与 JS 版本同样使用位运算取半返回min即最终答案注意List类型注解需从typing导入LeetCode 环境通常已内置。复杂度分析时间复杂度$O(N)$其中 $N$ 为数组长度。Set/set去重需要对数组做一次完整遍历哈希插入均摊 $O(1)$最终比较与取min为 $O(1)$空间复杂度$O(N)$最坏情况下所有糖果种类各不相同去重集合需要存储 $N$ 个不同元素。边界情况与变体思考边界情况验证均可直接套用公式输入种类数n/2输出说明[1,1,1,1]121种类数不足妹妹只能拿到 1 种[1,2,3,4]422种类数充足妹妹最多拿 2 种[1,2,1,2]222恰好相等两个约束同时生效[1,2,3,4,5,6]633全部不同答案恒为 n/2变体扩展供举一反三若把“平均分给两人”改为“平均分给 k 人”则答案泛化为min(种类数, n/k)思路完全一致——核心仍是“单人分到的糖果数量上限”与“总种类数”取小若题目要求弟弟和妹妹的种类数之和最大则问题退化为“能否在 n/2 个位置内装下更多种类”可结合贪心与计数进一步设计若把数组替换为流式输入在线场景可改用哈希表动态维护种类数在每读入一个元素后增量计算min(种类数, 已读长度/2)复杂度不变。在仓库中的定位与延伸阅读本题被收录在 collections/easy.md 的简单题合集以及 SUMMARY.md 的全局目录中可与其他简单题横向对比练习前置知识见 thinkings/basic-data-structure.md其中系统讲解了数组、集合等基础数据结构的典型应用同类“种类/去重 计数上限”的题目还包括仓库中的 575.distribute-candies.en.md英文版、136.single-number.md异或去重等可对照阅读加深对集合与位运算两种去重手段的理解。一句话总结分糖果问题本身不难真正的价值在于它训练了“先分析约束、再选择数据结构、最后写代码”的解题顺序——Set去重拿到种类数min与n 1完成上限约束四行代码即可 AC。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考