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ù)量就是糖果數(shù)組的一半，如果糖果種類大于數(shù)組的一半，說明妹妹可以拿到的糖果數(shù)量每一種都是不同的，糖果數(shù)量就是數(shù)組長度的一半，否則的話最多只能把所有糖果種類都拿一遍

代碼

class Solution { public:int distributeCandies(vector<int>& candyType) {unordered_set<int> set;for (auto a:candyType) set.insert(a);return set.size()>candyType.size()/2?candyType.size()/2:set.size();} }; 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的575. 分糖果的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。