Easy

题目描述

Alice 有 n 颗糖果，其中第 i 颗糖果的类型为 candyType[i]。Alice 注意到她开始变胖了，所以她去看了医生。

医生建议 Alice 只吃她拥有的糖果的 n / 2 颗（n 总是偶数）。Alice 非常喜欢她的糖果，她想在遵循医生建议的同时，尽可能多地吃不同类型的糖果。

给定长度为 n 的整数数组 candyType，如果 Alice 只吃其中的 n / 2 颗糖果，返回她能吃到的不同类型糖果的最大数量。

示例 1：

输入：candyType = [1,1,2,2,3,3]
输出：3
解释：Alice 只能吃 6 / 2 = 3 颗糖果。由于只有 3 种类型，她可以每种类型吃一颗。

示例 2：

输入：candyType = [1,1,2,3]
输出：2
解释：Alice 只能吃 4 / 2 = 2 颗糖果。无论她吃 [1,2]、[1,3] 还是 [2,3] 类型，她仍然只能吃 2 种不同的类型。

示例 3：

输入：candyType = [6,6,6,6]
输出：1
解释：Alice 只能吃 4 / 2 = 2 颗糖果。即使她可以吃 2 颗糖果，她也只有 1 种类型。

约束条件：

  • n == candyType.length
  • 2 <= n <= 10⁴
  • n 是偶数
  • -10⁵ <= candyType[i] <= 10⁵

解题思路

这是一道比较简单的贪心问题。我们需要理解的关键点是：要使吃到的糖果类型数最多，就应该优先选择不同类型的糖果。

解题思路：

  1. 分析约束条件：Alice 最多只能吃 n/2 颗糖果，同时我们希望最大化糖果类型数量。

  2. 关键观察：

    • 糖果的总类型数可能很多，也可能很少
    • Alice 能吃的糖果数量是固定的：n/2
    • 要最大化类型数，贪心策略是每种类型最多吃一颗

  3. 核心逻辑：

    • 统计糖果的不同类型数量（使用哈希表去重）
    • 答案是 min(不同类型数, n/2)
    • 如果类型数 >= n/2，那么可以吃 n/2 种不同类型
    • 如果类型数 < n/2，那么最多只能吃到所有类型数种

这个问题的本质是在有限的选择次数下，最大化选择的多样性。使用哈希表可以高效地统计不同类型的数量。

代码实现

class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        unordered_set<int> uniqueTypes;
        for (int candy : candyType) {
            uniqueTypes.insert(candy);
        }
        return min(uniqueTypes.size(), candyType.size() / 2);
    }
};

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

public class Solution {
    public int DistributeCandies(int[] candyType) {
        HashSet<int> uniqueTypes = new HashSet<int>(candyType);
        return Math.Min(uniqueTypes.Count, candyType.Length / 2);
    }
}

var distributeCandies = function(candyType) {
    const uniqueTypes = new Set(candyType);
    return Math.min(uniqueTypes.size, candyType.length / 2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历数组一次，哈希表操作为 O(1)
空间复杂度O(n)最坏情况下哈希表存储 n 个不同元素

相关题目