分糖果

题目

来源：力扣（LeetCode）
链接：分糖果

解法一

时间复杂度O(nlogn)
空间复杂度O(1)

int cmp(const void*a,const void *b){
    int *aa=(int*)a;
    int *bb=(int*)b;
    return *aa-*bb;
}
int distributeCandies(int* candies, int candiesSize){
    int kindnum=1;
    qsort(candies,candiesSize,sizeof(int),cmp);
    for(int i=1;i<candiesSize;i++){
        if(candies[i]!=candies[i-1]){
            kindnum++;
        }
        if(kindnum>=candiesSize/2)
            return candiesSize/2;
    }
   
    return kindnum;
}

解法二

时间复杂度O(n)
空间复杂度O(n)

class Solution {
public:
    int distributeCandies(vector<int>& candies) {
        set<int> kinds;
        for(int i=0;i<candies.size();i++){
            kinds.insert(candies[i]);
        }
        return min(kinds.size(),candies.size()/2);
    }
};