本文主要是介绍2021/11/01每日一题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

力扣：575. 分糖果

难度 简单

题目描述：

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

示例 1:

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

示例 2 :

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

注意:

1. 数组的长度为[2, 10,000]，并且确定为偶数。
2. 数组中数字的大小在范围[-100,000, 100,000]内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/distribute-candies
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题的解法有很多种，其中最高效的就是求出糖果种类数与总数的一半进行比较。顺着这个思路可以写出很多种不同的代码，以下就是本人第一次提交的代码：

class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        set<int> s;
        
        for (auto n : candyType) {
            s.insert(n);
        }
        
        return s.size() > candyType.size() / 2 ? candyType.size() / 2 : s.size();
    }
};

也可以写作：

class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        return min(set<int>(candyType.begin(), candyType.end()).size(), candyType.size() / 2);
    }
};

思路很清晰：

1. 将 vector 中的元素放入 set 中去。
2. 利用 set 的特性（元素无重复）可以直接调用 size 方法得到长度，同时就是糖果种类数。
3. 判断妹妹得到的最大糖果种类。

但是这种写法的用时和内存的情况是308ms/117.3MB，超过了17.264%/16.616%，非常不满意。

翻看了一下评论区，发现了一种写法：

Duge：

执行用时：156 ms, 在所有 C++ 提交中击败了92.13%的用户

内存消耗：79.7 MB, 在所有 C++ 提交中击败了95.98%的用户

统计糖果种类和重复的数量，重复糖果大于等于一半，妹妹可获得全部种类；小于一半，从剩余的糖果中补充给弟弟，妹妹获得种类则减去补充的数量

class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        sort(candyType.begin(), candyType.end());
        int type = 1, same = 0,n = candyType.size(), cur = candyType[0];
        for(int i = 1; i < n; i++) {
            if(candyType[i] != cur) {
                type++;
                cur = candyType[i];
            } else {
                same++;
            }
        }
        if(same >= n / 2) return type; 
        return type - (n / 2  - same);  
    }
};

大致的思路是一样的：

1. 计算种类。
2. 判断最大种类数.

但是他计算种类的方式却是先排序，再遍历，所以自己也按照这种思路写了一遍：

class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        sort(candyType.begin(), candyType.end());

        int type = 1, candy = candyType[0];

        for (auto candies : candyType) {
            if (candies != candy) {
                type++;
                candy = candies;
            }
        }

        return min(type, (int)candyType.size() / 2);
    }
};

这种写法的用时和内存的情况是106ms/78.8MB，超过了89.902%/88.274%，比Duge差了一点，分析之后认为这一点是因为使用的循环体是 for-in 循环，是从第 \(0\) 个元素开始遍历的，而且还会产生额外的内存开销，而且 min 函数也可能在重载过程中有内存的开销，导致最终的结果没有Duge好。

但是这种思路理论上是比第一种思路耗时更长，因为排序的时间复杂度为 \(O(n^2)\) 到 \(O(\log{n})\) 之间（平均时间复杂度为 \(O(n\log{n})\) ），而第一种方法的复杂度只有 \(O(n)\)，所以理论上的成绩两者应该是相反的。

但是如果深入到底层去看的话，将 vector 转换为 set 的实质就是将每个元素依次插入 set ，这也就是为什么第一种思路的两种写法运行结果几乎相同。而每一次的插入都必然会对现有的元素进行遍历以判断重复，所以需要 \(\frac{n(n+1)}{2}\)的时间，而这个时间甚至还没有计算重新为 set 分配空间等操作所花费的时间。所以第一种思路的执行用时更多。

而且由于新定义了一个 set ，内存的开销平均增加了 \(\frac{n}{2}\) ，所以内存消耗也更多。

这篇关于2021/11/01每日一题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！