题目：
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
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/distribute-candies
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
今天是完全不看题解，能直接写出来的简单题第3道。
一、模拟
我观察了一下示例，数组candyType的长度就为糖果的总数，于是先求出糖果的总数，再算出Alice能吃多少枚糖nums，因为有重复种类的糖果，就用set的去重特征把重复的糖果种类去掉，最终set集合中存在的是唯一的糖果种类
- 如果nums >= set.size()：说明能吃的数量大于糖果种类，但是种类只有额定数量，故最多也只能吃set.size()；
- 如果nums < set.size()：说明能吃的糖果数量小于糖果种类数，但是只能吃nums种。
java代码：
1 class Solution {
2 public int distributeCandies(int[] candyType) {
3 int n = candyType.length;
4 int nums = n / 2;
5 HashSet<Integer> set = new HashSet<>();
6 for(int i = 0; i < n; i++){
7 set.add(candyType[i]);
8 }
9 if(nums >= set.size()){
10 return set.size();
11 }else{
12 return nums;
13 }
14 }
15 }
python3一行代码：
1 class Solution: 2 def distributeCandies(self, candyType: List[int]) -> int: 3 return min(len(set(candyType)), len(candyType) // 2)
二、贪心法
思路跟上面的模拟差不多，写得具体一点
由于题目规定糖果数量 n为偶数，因此一定能将糖果平均分配成两份，能吃到的糖只有一半：n /2 ，假设糖果种类数量为 m，进行分情况讨论：
- 如果 m < n/2，那么，可以分得的糖果种类最多为 m 种，即每种糖果至少一颗。
- 如果 m > n/2，那么，可以分得的糖果种类为 n/2 种，即每种种类最多一颗。
- 如果 m = n/2，那么，每种正好分配一颗，即可得 m 种。
综上，最终可分得的糖果种类为 min(m, n/2)。
参考：@【彤哥来刷题啦】优化代码：https://leetcode.cn/problems/distribute-candies/solution/tong-ge-lai-shua-ti-la-yi-ti-liang-jie-t-74pf/
根据题目给定的数据范围为 [-100,000, 100,000]，比较小，所以，我们可以声明一个数组来模拟哈希表快速统计种类，并且，当种类的数量大于总数的一半时，就停止遍历了。
java代码：
1 class Solution {
2 public int distributeCandies(int[] candyType) {
3 //建立一个hash数组对candyType进行去重
4 boolean[] hash = new boolean[200001];
5 //用count来对candyType中不重复的数字即糖果种类进行计数
6 int count = 0;
7 for(int candy : candyType){
8 //candy + 100001 保证了 hash数组下标从0开始
9 //如果candy不重复，放入hash数组中
10 if(!hash[candy + 100000]){
11 count++;
12 hash[candy + 100000] = true;
13 //如果种类数已经大于等于糖果的一半，就不用再继续遍历了
14 if(count >= candyType.length / 2) break;
15 }
16 }
17 return count;
18 }
19 }
