575.-fen-tang-guo.md

575. 分糖果

https://leetcode-cn.com/problems/distribute-candies/

解法一：

思路:举例推演即可得以下结论: 假设数组长度为n,不同数字种类数为k, 1.若k < n/2 ,则sister最多拿到k种数. 2.若k > n/2,则由于sister和brother要相等的限制,sister最多也只能拿到n/2. 结论:sister最多拿到min(k, n/2)种.

用集合set即可统计不同数字的种类,考虑到无序集合unordered_set效率更高,速度更快.

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

#py
class Solution:
    def distributeCandies(self, candies: List[int]) -> int:
        n = len(candies)
        k = len(set(candies))
        return min(k, n//2)