575. 分糖果
給定一個偶數(shù)長度的數(shù)組，其中不同的數(shù)字代表著不同種類的糖果晌端，每一個數(shù)字代表一個糖果。你需要把這些糖果平均分給一個弟弟和一個妹妹诅蝶。返回妹妹可以獲得的最大糖果的種類數(shù)怕享。
示例 1:
輸入: candies = [1,1,2,2,3,3]
輸出: 3
解析: 一共有三種種類的糖果，每一種都有兩個砌滞。
最優(yōu)分配方案：妹妹獲得[1,2,3],弟弟也獲得[1,2,3]。這樣使妹妹獲得糖果的種類數(shù)最多坏怪。
示例 2 :
輸入: candies = [1,1,2,3]
輸出: 2
解析: 妹妹獲得糖果[2,3],弟弟獲得糖果[1,1]贝润，妹妹有兩種不同的糖果，弟弟只有一種铝宵。這樣使得妹妹可以獲得的糖果種類數(shù)最多打掘。
注意:
- 數(shù)組的長度為[2, 10,000]，并且確定為偶數(shù)鹏秋。
- 數(shù)組中數(shù)字的大小在范圍[-100,000, 100,000]內(nèi)尊蚁。
女孩能得到的唯一糖果的最大數(shù)量可以是 n/2，其中 nn 是指糖果的數(shù)量侣夷。此外横朋，如果獨特的糖果數(shù)量低于 n/2 的話，為了使女孩能得到的獨特的糖果數(shù)量最大化百拓，我們會將所有獨特的糖果分配給女孩琴锭。因此，在這種情況下衙传，女孩得到的獨特糖果數(shù)量等于給定 candiescandies 數(shù)組中的獨特糖果總數(shù)决帖。
我們可以對給定的 candiescandies 數(shù)組進行排序，并通過比較排序數(shù)組的相鄰元素來找出唯一的元素粪牲。對于找到的每個新元素（與前一個元素不同），我們需要更新 count止剖。最后腺阳，我們可以將所需結(jié)果返回為 min(n/2,count)，如前面的方法所述穿香。
class Solution {
public:
int distributeCandies(vector<int>& candyType) {
sort(candyType.begin(), candyType.end());
int count = 1;
for (int i = 1; i < candyType.size() && count < candyType.size() / 2; i++) {
if(candyType[i] > candyType[i - 1]) count++;
}
return count;
}
};
找到唯一元素數(shù)量的另一種方法是遍歷給定 candiescandies 數(shù)組的所有元素亭引，并繼續(xù)將元素放入集合中。通過集合的屬性皮获，它將只包含唯一的元素焙蚓。最后，我們可以計算集合中元素的數(shù)量洒宝，例如 countcount购公。要返回的值將再次由 \text{min}(count, n/2)min(count,n/2) 給出，如前面的方法所述雁歌。其中 nn 表示 candiescandies 數(shù)組的大小宏浩。
class Solution {
public:
int distributeCandies(vector<int>& candies) {
unordered_set<int> Set;
for (auto i:candies)
Set.insert(i);
return min(Set.size(), candies.size() / 2);
}
};
