企业官网建设流程全解析

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颗糖果。那么妹妹能获得的最大种类数取决于什么？只需要分两种情况讨论：

1. 糖果种类数大于n / 2：此时即使妹妹每颗糖都拿不同种类，她也只有n / 2颗糖，因此最多只能拿到n / 2种；
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 app=leetcode id=575 lang=javascript * * [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$ 个不同元素。

边界情况与变体思考

边界情况验证（均可直接套用公式）：

变体扩展（供举一反三）：

• 若把“平均分给两人”改为“平均分给 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