[leetcode] 575. Distribute Candies

[leetcode] 575. Distribute Candies

Description

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 = [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.

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/2，然后我们再看糖果的种类数，每个人拿到的糖果最大种类数不可能超过现有的糖果的种类数，所以这两者取最小值就是答案。这个要分析，分析出来了代码就比较简单了。

代码

class Solution {public: int distributeCandies(vector& candies) { unordered_set s; int cnt=0; for(int candy:candies){ s.insert(candy); cnt++; } return min((int)s.size(),cnt/2); }};

参考文献

​​[LeetCode] Distribute Candies 分糖果​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。