【leetcode刷题】T51-分糖果
【英文题目】（学习英语的同时，更能理解题意哟~）
Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.
Example 1:
Input: candies = [,,,,,]
Output:
Explanation:
There are three different kinds of candies (, and ), and two candies for each kind.
Optimal distribution: The sister has candies [,,] and the brother has candies [,,], too.
The sister has three different kinds of candies.
Example 2:
Input: candies = [,,,]
Output:
Explanation: For example, the sister has candies [,] and the brother has candies [,].
The sister has two different kinds of candies, the brother has only one kind of candies.
Note:
- The length of the given array is in range [2, 10,000], and will be even.
- The number in given array is in range [-100,000, 100,000].
【中文题目】
给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
示例 1:
输入: candies = [,,,,,]
输出:
解析: 一共有三种种类的糖果，每一种都有两个。
最优分配方案：妹妹获得[,,],弟弟也获得[,,]。这样使妹妹获得糖果的种类数最多。
示例 2 :
输入: candies = [,,,]
输出:
解析: 妹妹获得糖果[,],弟弟获得糖果[,]，妹妹有两种不同的糖果，弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。
注意:
- 数组的长度为[2, 10,000]，并且确定为偶数。
- 数组中数字的大小在范围[-100,000, 100,000]内。
【思路】
本题较为简单，能获得最多种类数的方法是：如果种类数超过n/2，则随便分一半种类数的糖果给妹妹；如果种类数小于n/2，则每一种优先分给妹妹。因此，结果为 min(n/2, m)。（n为糖果数，m为糖果的种类数）
【代码】
python版本
class Solution(object):
def distributeCandies(self, candies):
"""
:type candies: List[int]
:rtype: int
"""
return min(len(candies) // , len(set(candies)))
C++版本
class Solution {
public:
int distributeCandies(vector<int>& candies) {
set<int> s(candies.begin(), candies.end());
return min(candies.size() / , s.size());
}
};
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-04-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
