哈希算法题目：分糖果

题目描述
给定一个整数数组 candyType，表示糖果的类型。数组中的每个元素代表一颗糖果的类型。你的任务是计算妹妹最多能获得多少种不同类型的糖果，但需要遵循以下规则：她只能吃到 n/2 颗糖果（n 是糖果的总数）。

解题过程

1. 理解问题核心

   • 糖果总数是 n = candyType.length。
   • 妹妹最多可以吃 n/2 颗糖果。
   • 目标是让她吃到的糖果类型尽可能多。
   • 关键限制：即使糖果类型很多，她最多也只能吃 n/2 颗。

2. 关键观察

   • 设糖果类型总数为 typeCount（通过哈希集合统计不重复类型）。
   • 妹妹能吃的最大糖果数是 n/2。
   • 如果 typeCount >= n/2，她最多只能吃到 n/2 种类型（因为最多吃 n/2 颗）。
   • 如果 typeCount < n/2，她最多只能吃到 typeCount 种类型（类型数不足）。
   • 因此，实际结果是 min(typeCount, n/2)。

3. 算法步骤

   • 步骤1：遍历数组，用哈希集合存储所有糖果类型。
   • 步骤2：计算类型总数 typeCount = 集合大小。
   • 步骤3：返回 min(typeCount, n/2)。

4. 举例说明

   • 示例1：candyType = [1,1,2,2,3,3]
     • n = 6，妹妹可吃 3 颗。
     • 类型集合 {1,2,3}，typeCount = 3。
     • min(3, 3) = 3。她能吃到所有3种类型。
   • 示例2：candyType = [1,1,2,3]
     • n = 4，妹妹可吃 2 颗。
     • 类型集合 {1,2,3}，typeCount = 3。
     • min(3, 2) = 2。她只能吃到2种类型（尽管有3种）。

5. 复杂度分析

   • 时间复杂度：O(n)，遍历数组一次。
   • 空间复杂度：O(n)，哈希集合存储类型。

总结
通过哈希集合去重统计类型数，再与 n/2 比较取最小值，即可高效解决问题。