LeetCode-575

LeetCode-575 分糖果

题目
Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。
医生建议 Alice 只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要尽可能吃到最多不同种类的糖。
给一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的最多种类数。

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

题解

采用贪心的思想，由于只能分到一半的糖果 n ，所以分到的糖果种类不超过 n/2 ，由于糖果种类为 m 种，所以分到的糖果种类不超过 m ，因此，分到的糖果种类取 n/2 和 m 中的较小值。

更多题解

代码

unordered_set ：无序 set 容器
1）特性
a. 直接存储数据的值
b. 不允许重复且不能被修改
c. 不会对数据进行排序
2）初始化
a. 创建空的 set
unordered_set< int > set1;
b. 拷贝构造
unordered_set< int > set2(set1);
c. 使用迭代器构造
unordered_set< int > set3(set1.begin(), set1.end());
d. 使用数组构造
unordered_set< int > set4(arr,arr+5);
e. 移动构造
unordered_set< int > set5(move(set2));
f. 使用处置列表构造
unordered_set< int > set6 {1,2,10,10};

class Solution {
public:
    int distributeCandies(vector& candyType) {
        return min(unordered_set(candyType.begin(),candyType.end()).size(),candyType.size()/2);
    }
};