0575. Distribute Candies
========================
题目信息
--------
:题号: 0575
:难度: Easy
:主题: 糖果类型、固定分配数量、不同种类、最大化
:原题: `LeetCode 0575 `_
:重点: 糖果总数为偶数、妹妹必须得到恰好一半、同类型可重复、返回最多不同类型数
题目重述
--------
给定偶数长度数组 ``candyType``,每个元素表示一颗糖果的类型。所有糖果要平均分给哥哥和妹妹,因此妹妹会得到恰好 ``candyType.length / 2`` 颗糖果。
在可以自由选择分配方式的前提下,返回妹妹最多能够得到多少种不同类型的糖果。同一类型的多颗糖只贡献一种类型,但仍占用妹妹的糖果数量。
自建示例
--------
种类数多于妹妹可得数量:
.. code-block:: text
输入:candyType = [1,1,2,3,3,4]
输出:3
解释:妹妹只能得到 3 颗糖,可以各选类型 1、2、3 或其他三个不同类型,因此最多有 3 种。
全部糖果同类型:
.. code-block:: text
输入:candyType = [5,5,5,5]
输出:1
解释:妹妹得到两颗糖,但无论如何都只有类型 5。
不同类型数受两个上限约束
------------------------
妹妹最多拿 ``n/2`` 颗糖,因此不同类型数不可能超过这个数量;同时也不可能超过全部糖果中的不同类型总数。只要每种类型至少选一颗,取这两个上限的较小值就能构造出最优分配。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int distributeCandies(std::vector& candyType) {
std::unordered_set types(candyType.begin(),
candyType.end());
return std::min(static_cast(types.size()),
static_cast(candyType.size() / 2));
}
};
代码分析
--------
较小的上限是必要条件,按不同类型各取一颗并用重复糖果填满剩余数量即可达到,因此也是充分条件。时间复杂度为 ``O(n)`` 平均,额外空间复杂度为 ``O(n)``。