本文共 3457 字，大约阅读时间需要 11 分钟。

You have n candies, the ith candy is of type candies[i] .

You want to distribute the candies equally between a sister and a brother so that each of them gets n / 2 candies ( n is even). The sister loves to collect different types of candies, so you want to give her the maximum number of different types of candies.

Return the maximum number of different types of candies you can give to the sister.

Example 1:

Input: candies = [1,1,2,2,3,3]Output: 3Explanation:There are three different kinds of candies (1, 2 and 3), and two candies for each kind.Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too. The sister has three different kinds of candies.

Example 2:

Input: candies = [1,1,2,3]Output: 2Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1]. The sister has two different kinds of candies, the brother has only one kind of candies.

Example 3:

Input: candies = [1,1]Output: 1

Example 4:

Input: candies = [1,11]Output: 1

Example 5:

Input: candies = [2,2]Output: 1

Constraints:

• n == candies.length
• 2 <= n <= 10^4
• n is even.
• -10^5 <= candies[i] <= 10^5

题意：给定一个偶数长度的数组，不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。把这些糖果平均分给一个弟弟和一个妹妹，返回妹妹可得的最大糖果的种类数。

思路1 贪心

看到这个题目，想到的就是贪心，用 unordered_set 对糖果的种类进行去重，然后把这些种糖果尽可能分配给妹妹，直到分给妹妹 n / 2 个糖果或者没有更多种类为止。代码如下：

class Solution {
   public:    int distributeCandies(vector
   
    & candies) {
           int n = candies.size(), sisterCount = n / 2, ans = 0;        unordered_set
    
      record;        for (int i = 0; i < n; ++i) record.insert(candies[i]);        for (const auto &it : record) if (sisterCount-- > 0) ++ans;        return ans;     }};
    
   

效率比较低：

执行用时：624 ms, 在所有 C++ 提交中击败了53.61% 的用户内存消耗：112.8 MB, 在所有 C++ 提交中击败了37.95% 的用户

思路2 贪心+优化

如果 candies[] 数组中有 x 种糖果，然后将 x 种糖果尽可能分给妹妹，直到遍历完所有种糖果或者妹妹已经有了足够的糖果：

• x > n / 2 ，则妹妹得到的 n / 2 个糖果都是不同的（答案是 n / 2 种糖果），但是妹妹无法得到所有种类的糖果；
• x <= n / 2 ，则妹妹最多得到 x 种糖果，但是妹妹可以得到所有种类的糖果。

因此，答案就是 min(x, n / 2) 。代码如下：

class Solution {
   public:    int distributeCandies(vector
   
    & candies) {
           int n = candies.size(), size = 0;        unordered_set
    
      record;        for (int i = 0; i < n; ++i) record.insert(candies[i]);         //上两行可以修改为:        //unordered_set
     
       record(candies.begin(), candies.end());        size = record.size();        return min(n / 2, size);     }};
     
    
   

效率有所提高：

执行用时：580 ms, 在所有 C++ 提交中击败了76.39% 的用户内存消耗：112.8 MB, 在所有 C++ 提交中击败了39.94% 的用户

修改 unordered_set 为 vector<bool> ：

class Solution {
   public:    int distributeCandies(vector
   
    & candies) {
           int n = candies.size(), size = 0;          vector
    
      bucket(200010);        for (int i = 0; i < n; ++i) {
               if (!bucket[candies[i] + 100000]) {
                   ++size;                bucket[candies[i] + 100000] = true;            }        }        return min(n / 2, size);    }};
    
   

效率比起一开始几乎翻倍：

执行用时：372 ms, 在所有 C++ 提交中击败了96.64% 的用户内存消耗：86.1 MB, 在所有 C++ 提交中击败了79.41% 的用户

如果使用 bitset 呢？代码如下：

class Solution {
   public:    int distributeCandies(vector
   
    & candies) {
           int n = candies.size(), size = 0;          bitset<200010> bucket;        for (int i = 0; i < n; ++i) {
               if (!bucket[candies[i] + 100000]) {
                   ++size;                bucket[candies[i] + 100000] = 1;            }        }        return min(n / 2, size);    }};
   

效率又提高了一些：

执行用时：368 ms, 在所有 C++ 提交中击败了96.86% 的用户内存消耗：79.8 MB, 在所有 C++ 提交中击败了91.33% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/108810251 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！