题目描述

给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

样例

输入：candies = [1,1,2,2,3,3]
输出：3
解释：一共有三种种类的糖果，每一种都有两个。
     最优分配方案：妹妹获得 [1,2,3]，弟弟也获得 [1,2,3]。
     这样使妹妹获得糖果的种类数最多。

输入: candies = [1,1,2,3]
输出: 2
解释: 妹妹获得糖果 [2,3]，弟弟获得糖果 [1,1]，
     妹妹有两种不同的糖果，弟弟只有一种。
     这样使得妹妹可以获得的糖果种类数最多。

注意

• 数组的长度为 [2, 10000]，并且一定为偶数。
• 数组中数字的大小在范围 [-100000, 100000] 内。

算法

(哈希表) $O(n)$

1. 用 unordered_set 统计糖果的种类数，记为 count。
2. 尽量让妹妹一种拿一个，但最多不能超过 $\frac{size}{2}$ 种，故最终答案为 $\min (count, \frac{size}{2})$。

时间复杂度

• 用 unordered_set 统计种类数的时间复杂度为 $O(n)$，然后 $O(1)$ 判断，故总时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int distributeCandies(vector<int>& candies) {
        unordered_set<int> c;
        for (int x : candies)
            c.insert(x);

        return min(c.size(), candies.size() / 2);
    }
};