迅速百度网站自然排名,本地网站建设,长沙装修公司排名前十名,杭州互联网公司50强文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
哈希表
二【题目难度】
简单
三【题目编号】
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 ncandyType.length 2 n 1 0 4 2 n 10^4 2n104 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 −105candyType[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) {HashSetInteger 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(vectorint candyType) {return min(unordered_setint(candyType.begin(), candyType.end()).size(), candyType.size() / 2);}
};十【提交结果】 Java语言版 C语言版 Python语言版 C语言版
