575.分糖果

题目描述

分糖果

思路：贪心

根据题意，糖果数量n为偶数，因此必定能将糖果平均分为两份，每份数量都为n/2。
假设糖果种类数量为m，则单份糖果中种类的最大数量为min(m, n/2)。
证明过程如下：

1. m > n/2时，糖果种类大于单份的糖果数量，此时，可以从m类糖果中取出n/2类不同的糖果组成单份，此时可取得最大种类数为n/2；
2. m = n/2时，糖果种类等于单份的糖果数量，此时，可以从糖果中取出n/2类糖果组成单份，此时可取得的最大种类数为n/2 = m；
3. m < n/2时，糖果种类小于单份的糖果数量，此时，可以从糖果中取出m类糖果组成单份，再使用n/2-m个相同种类的糖果凑齐n/2，此时可以取得的最大种类数量为m。
   综上所述，最多种类数为min(m, n/2)。

Java实现

class Solution {public int distributeCandies(int[] candyType) {Set<Integer> set = new HashSet<>();for (int i : candyType) set.add(i);return Math.min(candyType.length/2, set.size());}
}

Python实现

class Solution:def distributeCandies(self, candyType: List[int]) -> int:return min(len(candyType)//2, len(set(candyType)))