【LeetCode每日一题】——575.分糖果

一【题目类别】

• 哈希表

二【题目难度】

• 简单

三【题目编号】

• 575.分糖果

四【题目描述】

• 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<=10^4$
• $n是一个偶数$
• $-10^5<=candyType[i]<=10^5$

七【解题思路】

• 因为糖果的个数总共为$n$个，所以根据题意，最后返回的结果不会超过$\frac{n}{2}$
• 此外，设这些糖果一共有$m$种，所以说返回的结果也不会超过$m$
• 如果$m\le \frac{n}{2}$，那么说明可以吃到重复的糖果，但是最多吃到$m$种糖果，返回的结果就是$m$
• 如果$m\ge \frac{n}{2}$，那么说明就算有再多的糖果种类，也只能吃到$\frac{n}{2}$颗糖果
• 综上所述，最后返回的结果为：$min(m,\frac{n}{2})$
• 实现以上思路使用哈希表即可，比较简单，具体内容可参见下面的代码
• 最后返回结果即可

八【时间频度】

• 时间复杂度：$O(n)$，$n$为传入的数组的长度
• 空间复杂度：$O(n)$，$n$为传入的数组的长度

九【代码实现】

1. Java语言版

class Solution {public int distributeCandies(int[] candyType) {HashSet<Integer> set = new HashSet<>();for(int i = 0;i < candyType.length;i++){set.add(candyType[i]);}return Math.min(set.size(), candyType.length / 2);}
}

2. C语言版

int distributeCandies(int* candyType, int candyTypeSize)
{int* map = (int*)calloc(200001, sizeof(int));for(int i = 0;i < candyTypeSize;i++){map[candyType[i] + 100000]++;}int count = 0;for(int i = 0;i < 200001;i++){if(map[i] > 0){count++;}}return fmin(count, candyTypeSize / 2);
}

3. Python语言版

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

4. C++语言版

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

十【提交结果】

1. Java语言版
   

2. C语言版
   

3. Python语言版
   

4. C++语言版