分糖果

标签: 数组 哈希表

难度: 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]，她只能吃到两种不同类的糖。

示例 3：

输入：candyType = [6,6,6,6]
输出：1
解释：Alice 只能吃 4 / 2 = 2 枚糖，尽管她能吃 2 枚，但只能吃到 1 种糖。

提示：

  • n == candyType.length
  • 2 <= n <= 104
  • n 是一个偶数
  • -105 <= candyType[i] <= 105

Submission

运行时间: 54 ms

内存: 17.4 MB

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

Explain

题解的核心思路是利用集合去除数组 candyType 中重复的元素，从而得到所有糖果的种类数。由于 Alice 只能吃掉 n/2 枚糖果，题目转化为计算最大的不同种类数和 n/2 的较小值。如果不同种类数超过 n/2，则答案是 n/2，因为 Alice 最多只能吃 n/2 枚；如果种类数少于 n/2，则答案是所有种类的数量，因为 Alice 可以尝试每种各吃一枚。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        # 将 candyType 数组转化为集合，去除重复元素，得到所有糖果的种类
        unique_candies = set(candyType)
        # 计算她可以吃的糖果数目的一半
        max_candies_she_can_eat = len(candyType) // 2
        # 返回可吃的最大糖果种类数，即 unique_candies 的长度和 max_candies_she_can_eat 中的较小者
        return min(len(unique_candies), max_candies_she_can_eat)

Explore

在Python中，集合（set）是一个不包含重复元素的数据结构。当我们将列表（list）转换为集合时，Python自动移除列表中的所有重复元素。因此，通过简单地将candyType数组转换为集合，所有的重复糖果种类都被自动剔除，保证了集合中每种糖果的唯一性。这个转换过程由Python内部优化处理，效率较高。

使用集合（set）存储糖果种类的主要原因是集合具有高效的查找和插入性能，且能自动处理重复元素。与之相比，使用列表（list）可能需要手动检查重复元素，且查找和插入操作的时间复杂度为O(n)。虽然字典（dictionary）也能提供类似的性能优势，但使用集合更直接，因为我们只关心糖果种类的存在性，而不需要存储额外的键值对信息。

如果unique_candies的长度与max_candies_she_can_eat相等，这意味着Alice可以尝试每一种糖果，而且数量刚好等于她能吃的最大糖果数。在这种情况下，算法的输出将是这两个相等的值。性能方面，这种情况不会对算法造成任何额外的计算负担，因为无论结果如何，比较操作的复杂度都是O(1)，非常高效。

如果candyType数组中的所有元素都相同，转换为集合后，集合中只会有一个元素。这种情况下，算法仍然高效执行，因为将数组转换为集合的时间复杂度是O(n)，而后续的操作（比较长度和取最小值）的时间复杂度为O(1)。总体来说，算法面对这种极端情况仍能保持较高效率。