575. Distribute Candies

1. Question

Alice has n candies, where the i^th candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.

The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor's advice.

Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.

2. Examples

Example 1:

Input: candyType = [1,1,2,2,3,3]
Output: 3
Explanation: Alice can only eat 6 / 2 = 3 candies. Since there are only 3 types, she can eat one of each type.

Example 2:

Input: candyType = [1,1,2,3]
Output: 2
Explanation: Alice can only eat 4 / 2 = 2 candies. Whether she eats types [1,2], [1,3], or [2,3], she still can only eat 2 different types.

Example 3:

Input: candyType = [6,6,6,6]
Output: 1
Explanation: Alice can only eat 4 / 2 = 2 candies. Even though she can eat 2 candies, she only has 1 type.

3. Constraints

• n == candyType.length
• 2 <= n <= 10⁴
• n is even.
• -10⁵ <= candyType[i] <= 10⁵

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/distribute-candies 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

答案不超过总数量n的1/2，同时不超过糖果的种类数n。如果m <= n/2，则可以多给相同种类的糖果以达到总数的一半。如果m > n/2，则最多只能分到n/2种糖果。所以答案只有可能是二者的最小者。

结合条件，总数量为偶数，所以不用考虑整除问题。

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