LintCode：1163 · 分糖果

问题描述

给定长度为偶数的整数数组，该数组中不同的数字代表不同种类的糖果， 每个数字表示一种糖果。 您需要将这些糖果平均分配给弟弟和妹妹。 返回妹妹可以获得的糖果种类的最大数量。

备注：
1.所给数组的长度范围为[2, 10,000]，且为偶数。
2.所给数组中数字的范围为[-100,000, 100,000]。

样例

输入: candies = [1,1,2,2,3,3]
输出: 3
解释:
有三种不同的糖果(1, 2 and 3), 每种糖果有两个。
最佳分法：妹妹拥有[1,2,3] ，弟弟也会拥有拥有[1,2,3]。
妹妹拥有3种不同的糖果。

解题思路

1. 弟弟和妹妹是平分的。也就是说，假设有n个糖果（输入的数组长度是偶数），弟弟和妹妹每人必定分到n/2个糖果；
2. 要求妹妹可以获得糖果种类的最大数量，那么我们必定要求出有多少种糖果，我们记为k；
3. 然后分析可能的几种情况：
   A. 糖果种类k大于允许分到的数量n/2，那么妹妹可以获得的糖果种类的最大数量为n/2;
   B. 糖果种类k小于等于允许分到的数量n/2，那么妹妹可以获得的糖果种类的最大数量为k。
   换句话说，就是要取n/2、k之间的min。

代码示例（JAVA）

public class Solution {
    /**
     * @param candies: a list of integers
     * @return: return a integer
     */
    public int distributeCandies(int[] candies) {
        TreeSet<Integer> kinds = new TreeSet<Integer>();
        for (int candy: candies) {
            kinds.add(candy);
        }
        
        return Math.min(candies.length / 2, kinds.size());
    }
}