一【题目类别】
- 哈希表
二【题目难度】
- 简单
三【题目编号】
- 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 = = c a n d y T y p e . l e n g t h n == candyType.length n==candyType.length
- 2 < = n < = 1 0 4 2 <= n <= 10^4 2<=n<=104
- n 是一个偶数 n 是一个偶数 n是一个偶数
- − 1 0 5 < = c a n d y T y p e [ i ] < = 1 0 5 -10^5 <= candyType[i] <= 10^5 −105<=candyType[i]<=105
七【解题思路】
- 因为糖果的个数总共为 n n n个，所以根据题意，最后返回的结果不会超过 n 2 \frac{n}{2} 2n
- 此外，设这些糖果一共有 m m m种，所以说返回的结果也不会超过 m m m
- 如果 m ≤ n 2 m \leq \frac{n}{2} m≤2n，那么说明可以吃到重复的糖果，但是最多吃到 m m m种糖果，返回的结果就是 m m m
- 如果 m ≥ n 2 m \geq \frac{n}{2} m≥2n，那么说明就算有再多的糖果种类，也只能吃到 n 2 \frac{n}{2} 2n颗糖果
- 综上所述，最后返回的结果为： m i n ( m , n 2 ) min(m, \frac{n}{2}) min(m,2n)
- 实现以上思路使用哈希表即可，比较简单，具体内容可参见下面的代码
- 最后返回结果即可
八【时间频度】
- 时间复杂度： O ( n ) O(n) O(n)， n n n为传入的数组的长度
- 空间复杂度： O ( n ) O(n) O(n)， n n n为传入的数组的长度
九【代码实现】
- 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);
}
}
- 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);
}
- Python语言版
class Solution:
def distributeCandies(self, candyType: List[int]) -> int:
return min(len(set(candyType)), len(candyType) // 2)
- C++语言版
class Solution {
public:
int distributeCandies(vector<int>& candyType) {
return min(unordered_set<int>(candyType.begin(), candyType.end()).size(), candyType.size() / 2);
}
};
十【提交结果】
-
Java语言版
-
C语言版
-
Python语言版
文章来源：https://www.toymoban.com/news/detail-636670.html -
C++语言版
文章来源地址https://www.toymoban.com/news/detail-636670.html
到了这里，关于【LeetCode每日一题】——575.分糖果的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
