原文链接: https://leetcode-cn.com/problems/distribute-candies

英文原文

Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.

The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor's advice.

Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.

 

Example 1:

Input: candyType = [1,1,2,2,3,3]
Output: 3
Explanation: Alice can only eat 6 / 2 = 3 candies. Since there are only 3 types, she can eat one of each type.

Example 2:

Input: candyType = [1,1,2,3]
Output: 2
Explanation: Alice can only eat 4 / 2 = 2 candies. Whether she eats types [1,2], [1,3], or [2,3], she still can only eat 2 different types.

Example 3:

Input: candyType = [6,6,6,6]
Output: 1
Explanation: Alice can only eat 4 / 2 = 2 candies. Even though she can eat 2 candies, she only has 1 type.

 

Constraints:

• n == candyType.length
• 2 <= n <= 104
• n is even.
• -105 <= candyType[i] <= 105

中文题目

Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。

医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。

给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的最多种类数。

 

示例 1：

输入：candyType = [1,1,2,2,3,3]
输出：3
解释：Alice 只能吃 6 / 2 = 3 枚糖，由于只有 3 种糖，她可以每种吃一枚。

示例 2：

输入：candyType = [1,1,2,3]
输出：2
解释：Alice 只能吃 4 / 2 = 2 枚糖，不管她选择吃的种类是 [1,2]、[1,3] 还是 [2,3]，她只能吃到两种不同类的糖。

示例 3：

输入：candyType = [6,6,6,6]
输出：1
解释：Alice 只能吃 4 / 2 = 2 枚糖，尽管她能吃 2 枚，但只能吃到 1 种糖。

 

提示：

• n == candyType.length
• 2 <= n <= 104
• n 是一个偶数
• -105 <= candyType[i] <= 105

通过代码

高赞题解

贪心

由于题目规定糖果数量 $n$ 为偶数，因此一定能将糖果平均分配成两份，每份数量固定为 $\frac{n}{2}$。

假设糖果种类数量为 $m$，那么单份中可使得糖果种类数量最大为 $\min(m, \frac{n}{2})$。

可以使用「分情况讨论」进行证明：

1. $m > \frac{n}{2}$：糖果种类大于单份的糖果数量。此时可以从 $m$ 类糖果中找出 $\frac{n}{2}$ 类不同的糖果组成单份，此时可取得的最大种类数量为 $\frac{n}{2}$；

2. $m = \frac{n}{2}$：糖果种类等于单份的糖果数量。同理，此时可以从 $m$ 类糖果中找出 $\frac{n}{2}$ 类不同的糖果组成单份，此时可取得的最大种类数量为 $m = \frac{n}{2}$；

3. $m < \frac{n}{2}$：糖果种类小于单份的糖果数量。此时先从 $m$ 类糖果中找出 $m$ 类不同糖果组成单份，再使用相同种类的糖果凑齐 $\frac{n}{2}$，此时可取得的最大种类数量为 $m$。

综上，无论糖果种类数与单份糖果数呈何种关系，我们可取得的最大糖果种类数量均为 $\min(m, \frac{n}{2})$。

代码（使用数组代替常数较大的 Set 结构的代码在 $P2$）：

[]
class Solution {
    public int distributeCandies(int[] candyType) {
        Set<Integer> set = new HashSet<>();
        for (int i : candyType) set.add(i);
        return Math.min(candyType.length / 2, set.size());
    }
}

[]
class Solution {
    public int distributeCandies(int[] candyType) {
        boolean[] hash = new boolean[200005];
        int cnt = 0;
        for (int i : candyType) {
            if (!hash[i + 100001] && ++cnt >= 0) hash[i + 100001] = true;
        }
        return Math.min(cnt, candyType.length / 2);
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

其他「相信科学」系列内容

题太简单？不如来学习一道 面试高频题（文末含送书彩蛋）~

或是考虑加练如下「贪心/相信科学」系列内容 🍭🍭🍭

题目	题解	难度	推荐指数
11. 盛最多水的容器	LeetCode 题解链接	中等	🤩🤩🤩🤩🤩
45. 跳跃游戏 II	LeetCode 题解链接	中等	🤩🤩🤩🤩
179. 最大数	LeetCode 题解链接	中等	🤩🤩🤩🤩
502. IPO	LeetCode 题解链接	困难	🤩🤩🤩
517. 超级洗衣机	LeetCode 题解链接	困难	🤩🤩🤩
524. 通过删除字母匹配到字典里最长单词	LeetCode 题解链接	中等	🤩🤩🤩🤩
561. 数组拆分 I	LeetCode 题解链接	简单	🤩🤩🤩🤩
575. 分糖果	LeetCode 题解链接	简单	🤩🤩🤩🤩
765. 情侣牵手	LeetCode 题解链接	困难	🤩🤩🤩
781. 森林中的兔子	LeetCode 题解链接	中等	🤩🤩🤩🤩
881. 救生艇	LeetCode 题解链接	中等	🤩🤩🤩🤩
995. K 连续位的最小翻转次数	LeetCode 题解链接	困难	🤩🤩🤩
1221. 分割平衡字符串	LeetCode 题解链接	简单	🤩🤩🤩🤩
1707. 与数组中元素的最大异或值	LeetCode 题解链接	困难	🤩🤩🤩
1713. 得到子序列的最少操作次数	LeetCode 题解链接	困难	🤩🤩🤩🤩🤩
1736. 替换隐藏数字得到的最晚时间	LeetCode 题解链接	简单	🤩🤩🤩🤩🤩
1833. 雪糕的最大数量	LeetCode 题解链接	中等	🤩🤩🤩🤩🤩
1846. 减小和重新排列数组后的最大元素	LeetCode 题解链接	中等	🤩🤩🤩🤩🤩
1877. 数组中最大数对和的最小值	LeetCode 题解链接	中等	🤩🤩🤩🤩🤩

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
86341	121144	71.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言