LeetCode 575.分糖果
原题链接 11.1
题目描述：
给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
证明：
设总糖果数为 , 两个人要平分糖果，则每个人能拿到的糖果数为
，设妹妹得到的糖果总类数是
，总的糖果类是
：
- 当
，说明
，即妹妹将每个种类的糖果各拿一个，其余平分
- 当
，说明
，妹妹最多只能拿
种糖果
代码：
class Solution {
public:
int distributeCandies(vector<int>& candyType) {
unordered_set<int> S;
for (auto c : candyType) S.insert(c);
return min(candyType.size() / 2, S.size());
}
};
使用set来保存糖果总类数
