LeetCode 575. 分糖果

约 3 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节 华为
标签
数组 哈希表

题目描述

✅ 575. 分糖果

image-20260928224319234

image-20260928224319235

题意分析

从 n 颗糖中选出 n/2 颗，使选到的不同种类最多，题目保证 n 为偶数。相同种类可以选多颗，但对种类数只贡献一次；类型编号只用来判断是否相同，大小和正负没有其他含义。

解法：去重计数

核心思路

[!blue]

设全部糖果共有 u 种，可以选的颗数为 limit=n/2。答案不可能超过已有种类数 u；每得到一种还至少需要占用一个名额，所以也不能超过 limit。因此 min(u,limit) 是上界。

这个上界一定能达到。若 u >= limit，选出 limit 个不同种类，每种拿一颗即可；若 u < limit，先从每种拿一颗，再从剩余糖果中任意补足颗数，仍然保留全部 u 种。原来共有 n 颗糖，补足到 n/2 总有足够的剩余糖果。

既然最优值只取决于不同种类的数量，用集合去重即可，无需记录每种具体出现几次，也无需实际构造选择方案。

解题步骤

  • 用集合统计不同编号。
  • 可选颗数为原数组长度的一半。
  • 返回种类数与颗数上限的较小值。

全部糖果同类时答案为 1；所有糖果都不同类时，答案由名额限制为 n/2。

代码实现

class Solution {
    public int distributeCandies(int[] candyType) {
        Set<Integer> set = new HashSet<>();

        for (int t : candyType) {
            set.add(t);
        }

        // 不同种类数同时受已有种类与可选颗数限制
        return Math.min(set.size(), candyType.length / 2);
    }
}

func distributeCandies(candyType []int) int {
    set := make(map[int]struct{})
    for _, v := range candyType {
        set[v] = struct{}{}
    }

    // 不同种类数同时受已有种类与可选颗数限制
    limit := len(candyType) / 2
    if len(set) < limit {
        return len(set)
    }
    return limit
}

复杂度分析

  • 时间复杂度：期望 $O(n)$，扫描一次并去重。
  • 空间复杂度：$O(u)$，其中 u 为全部糖果的不同种类数。

关键点总结

[!green]

  • 总种类数和可选颗数共同给出上界。
  • 两种情况下都能构造达到上界的选择，取较小值才是确切答案。

易错点总结

[!yellow]

  • 只返回种类数，会超过可选颗数。
  • 只返回一半长度，会高估全相同的情况。
  • 用去重后的长度除二，混淆了种类与颗数。

相似题目

题目 难度 关联与区别
2357. 使数组中所有元素都等于零 简单 同样先识别答案与不同数值种类的关系，本题还受只能拿总数一半的容量限制。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/20091563
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！