class Solution {
public:
int distributeCandies(vector<int>& candyType) {
}
};
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.length2 <= n <= 104n 是一个偶数-105 <= candyType[i] <= 105原站题解
rust 解法, 执行用时: 22 ms, 内存消耗: 2.2 MB, 提交时间: 2024-06-02 09:45:48
use std::collections::HashSet;
impl Solution {
pub fn distribute_candies(candy_type: Vec<i32>) -> i32 {
let set = candy_type.iter().collect::<HashSet<_>>();
set.len().min(candy_type.len() / 2) as _
}
}
cpp 解法, 执行用时: 208 ms, 内存消耗: 117 MB, 提交时间: 2024-06-02 09:45:20
class Solution {
public:
int distributeCandies(vector<int> &candyType) {
return min(unordered_set<int>(candyType.begin(), candyType.end()).size(), candyType.size() / 2);
}
};
java 解法, 执行用时: 32 ms, 内存消耗: 44.4 MB, 提交时间: 2024-06-02 09:44:59
class Solution {
public int distributeCandies(int[] candyType) {
Set<Integer> set = new HashSet<Integer>();
for (int candy : candyType) {
set.add(candy);
}
return Math.min(set.size(), candyType.length / 2);
}
}
javascript 解法, 执行用时: 93 ms, 内存消耗: 62.8 MB, 提交时间: 2024-06-02 09:44:41
/**
* @param {number[]} candyType
* @return {number}
*/
var distributeCandies = function(candyType) {
const set = new Set(candyType);
return Math.min(set.size, candyType.length / 2);
};
golang 解法, 执行用时: 123 ms, 内存消耗: 7.3 MB, 提交时间: 2024-06-02 09:44:23
func distributeCandies(candyType []int) int {
set := map[int]struct{}{}
for _, t := range candyType {
set[t] = struct{}{}
}
ans := len(candyType) / 2
if len(set) < ans {
ans = len(set)
}
return ans
}
python3 解法, 执行用时: 85 ms, 内存消耗: 18 MB, 提交时间: 2024-06-02 09:44:03
class Solution:
def distributeCandies(self, candyType: List[int]) -> int:
return min(len(set(candyType)), len(candyType) // 2)
golang 解法, 执行用时: 236 ms, 内存消耗: 7.1 MB, 提交时间: 2021-06-11 14:42:48
func distributeCandies(candyType []int) int {
sort.Ints(candyType)
count := 1
for i := 1; i < len(candyType); i++ {
if candyType[i] != candyType[i-1] {
count++
}
}
return min(count, len(candyType)/2)
}
func min(x, y int) int {
if x > y {
return y
}
return x
}