哈希算法题目：分糖果

字数 2089 2025-12-11 06:39:34

哈希算法题目：分糖果

题目描述

给定一个长度为 n 的整数数组 candyType，其中 candyType[i] 表示第 i 颗糖果的类型。你是一个医生，需要遵循以下建议：你妹妹最多只能吃 n / 2 颗糖（n 是糖果总数），但你希望她在限量内吃到尽可能多种类的糖果。请注意，不同的数字代表不同种类的糖果。目标是返回她可以吃到的糖果种类的最大数量。

简单来说，就是从数组中，选出最多 n/2 个糖果，使得选中的糖果种类数尽可能多。返回这个最大的种类数。

示例 1：
输入：candyType = [1,1,2,2,3,3]
输出：3
解释：糖果类型为 1, 2, 3 三种。糖果总数为 6，最多能吃 3 颗。最优策略是每种类型吃一颗，总共可以吃到 3 种。

示例 2：
输入：candyType = [1,1,2,3]
输出：2
解释：糖果类型为 1, 2, 3 三种。糖果总数为 4，最多能吃 2 颗。虽然种类有3种，但最多只能选2颗糖，所以最多只能吃到 2 种（例如，类型1和类型2各一颗）。

示例 3：
输入：candyType = [6,6,6,6]
输出：1
解释：只有一种糖果类型，即使最多能吃 2 颗，也只能吃到 1 种。

核心思路与解题过程

这个问题的关键在于理解限制条件和目标之间的平衡。

问题分析：
- 已知条件：糖果总数为 n，糖果类型数组为 candyType。
- 限制条件：最多可以吃的糖果数量为 limit = n / 2。
- 目标：在不超过 limit 的前提下，最大化吃到的糖果种类数。
- 隐含信息：吃糖时，同一种类的糖果可以只吃一颗，就能“获得”该种类。因为目标是种类数，而不是某种类的数量。
关键洞察：
我们可以从两个角度来看这个“上限”：
- 种类数量上限：糖果的总种类数 typeCount 是你能吃到的种类数的绝对上限。即使你可以吃很多糖，你最多也只能吃到 typeCount 种。
- 数量上限：医生给出的建议是硬性数量限制 limit = n / 2。你吃的糖总数不能超过这个数。
因此，你实际能吃到的最大种类数，是由 typeCount 和 limit 中较小的那个决定的。
- 如果 typeCount <= limit，这意味着糖果的种类本身就不多，即使医生允许你吃 limit 颗，你最多也只能找到 typeCount 种不同的糖果来各吃一颗。所以答案是 typeCount。
- 如果 typeCount > limit，这意味着糖果种类很丰富，超过了你能吃的数量上限。即使你想品尝所有种类，你最多也只能吃 limit 颗，所以你也只能吃到 limit 种（每种吃一颗）。所以答案是 limit。
结论：答案为 min(typeCount, n / 2)。
引入哈希表：
现在，问题转化为如何高效地求出糖果的总种类数 typeCount。因为数组 candyType 中可能有重复的数字。
- 暴力去重：对数组排序，然后遍历统计不同数字，时间复杂度 O(n log n)。
- 哈希表法：使用哈希集合（HashSet），其核心特性是自动去重。我们只需要遍历一次数组，将每个糖果类型放入哈希集合中。遍历结束后，哈希集合的大小就是糖果的总种类数 typeCount。这种方法平均时间复杂度为 O(n)，空间复杂度为 O(n)（最坏情况是所有糖果类型都不同）。
详细步骤拆解：
- 步骤1：计算数量上限。
  计算 limit = candyType.length / 2。注意在大多数编程语言中，整数除法会自动向下取整，这符合“最多吃 n/2 颗”的数学定义。
- 步骤2：计算糖果总种类数。
  1. 初始化一个空的哈希集合 set。
  2. 遍历数组 candyType 中的每一个元素 type。
  3. 将 type 添加到 set 中。由于集合的性质，重复的 type 不会被重复添加。
  4. 遍历结束后，set 的大小（set.size()）即为糖果的总种类数 typeCount。
- 步骤3：计算最终答案。
  比较 typeCount 和 limit，返回两者中的较小值。result = min(typeCount, limit)。
举例验证：
以示例2 candyType = [1,1,2,3] 为例：
- n = 4, limit = 4 / 2 = 2。
- 遍历数组，set 最终包含 {1, 2, 3}，typeCount = 3。
- min(3, 2) = 2。符合题意。

总结
这道题巧妙地运用了哈希集合去重的核心能力，快速统计出不重复元素的个数。解题的核心逻辑在于理解“最大种类数”受到 实际种类数 和 医生规定的数量上限 两者的共同制约，结果是两者的最小值。哈希表在这里的作用是高效地解决了“统计不重复元素个数”这个子问题。

哈希算法题目：分糖果题目描述给定一个长度为 n 的整数数组 candyType ，其中 candyType[i] 表示第 i 颗糖果的类型。你是一个医生，需要遵循以下建议：你妹妹最多只能吃 n / 2 颗糖（n 是糖果总数），但你希望她在限量内吃到尽可能多种类的糖果。请注意，不同的数字代表不同种类的糖果。目标是返回她可以吃到的糖果种类的最大数量。简单来说，就是从数组中，选出最多 n/2 个糖果，使得选中的糖果种类数尽可能多。返回这个最大的种类数。示例 1：输入：candyType = [ 1,1,2,2,3,3 ] 输出：3 解释：糖果类型为 1, 2, 3 三种。糖果总数为 6，最多能吃 3 颗。最优策略是每种类型吃一颗，总共可以吃到 3 种。示例 2：输入：candyType = [ 1,1,2,3 ] 输出：2 解释：糖果类型为 1, 2, 3 三种。糖果总数为 4，最多能吃 2 颗。虽然种类有3种，但最多只能选2颗糖，所以最多只能吃到 2 种（例如，类型1和类型2各一颗）。示例 3：输入：candyType = [ 6,6,6,6 ] 输出：1 解释：只有一种糖果类型，即使最多能吃 2 颗，也只能吃到 1 种。核心思路与解题过程这个问题的关键在于理解限制条件和目标之间的平衡。问题分析：已知条件：糖果总数为 n ，糖果类型数组为 candyType 。限制条件：最多可以吃的糖果数量为 limit = n / 2 。目标：在不超过 limit 的前提下，最大化吃到的糖果种类数。隐含信息：吃糖时，同一种类的糖果可以只吃一颗，就能“获得”该种类。因为目标是种类数，而不是某种类的数量。关键洞察：我们可以从两个角度来看这个“上限”：种类数量上限：糖果的总种类数 typeCount 是你能吃到的种类数的绝对上限。即使你可以吃很多糖，你最多也只能吃到 typeCount 种。数量上限：医生给出的建议是硬性数量限制 limit = n / 2 。你吃的糖总数不能超过这个数。因此，你实际能吃到的最大种类数，是由 typeCount 和 limit 中较小的那个决定的。如果 typeCount <= limit ，这意味着糖果的种类本身就不多，即使医生允许你吃 limit 颗，你最多也只能找到 typeCount 种不同的糖果来各吃一颗。所以答案是 typeCount 。如果 typeCount > limit ，这意味着糖果种类很丰富，超过了你能吃的数量上限。即使你想品尝所有种类，你最多也只能吃 limit 颗，所以你也只能吃到 limit 种（每种吃一颗）。所以答案是 limit 。结论：答案为 min(typeCount, n / 2) 。引入哈希表：现在，问题转化为如何高效地求出糖果的总种类数 typeCount 。因为数组 candyType 中可能有重复的数字。暴力去重：对数组排序，然后遍历统计不同数字，时间复杂度 O(n log n)。哈希表法：使用哈希集合（HashSet），其核心特性是自动去重。我们只需要遍历一次数组，将每个糖果类型放入哈希集合中。遍历结束后，哈希集合的大小就是糖果的总种类数 typeCount 。这种方法平均时间复杂度为 O(n)，空间复杂度为 O(n)（最坏情况是所有糖果类型都不同）。详细步骤拆解：步骤1：计算数量上限。计算 limit = candyType.length / 2 。注意在大多数编程语言中，整数除法会自动向下取整，这符合“最多吃 n/2 颗”的数学定义。步骤2：计算糖果总种类数。初始化一个空的哈希集合 set 。遍历数组 candyType 中的每一个元素 type 。将 type 添加到 set 中。由于集合的性质，重复的 type 不会被重复添加。遍历结束后， set 的大小（ set.size() ）即为糖果的总种类数 typeCount 。步骤3：计算最终答案。比较 typeCount 和 limit ，返回两者中的较小值。 result = min(typeCount, limit) 。举例验证：以示例2 candyType = [1,1,2,3] 为例： n = 4 , limit = 4 / 2 = 2 。遍历数组， set 最终包含 {1, 2, 3} ， typeCount = 3 。 min(3, 2) = 2 。符合题意。总结这道题巧妙地运用了哈希集合去重的核心能力，快速统计出不重复元素的个数。解题的核心逻辑在于理解“最大种类数”受到实际种类数和医生规定的数量上限两者的共同制约，结果是两者的最小值。哈希表在这里的作用是高效地解决了“统计不重复元素个数”这个子问题。