力扣每日一题-第29天-575.分糖果

2022.6.27今天你刷题了吗？

---

题目：

Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。

医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。

给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的 最多 种类数。

分析：

给你一个偶数数组，你需要找到数组大小的一半的值x，和不同元素的类型y进行比较，如果x大于等于y，则返回y，否则返回x。

思路：我们利用map容器把元素插入，然后根据map的大小和原数组一半大小进行比较可以得到结果

解析：

1.哈希表

class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        unordered_map<int, int>map;
        int n = candyType.size() / 2;
        int res = 0;
        for (auto num : candyType)
        {
            map[num]++;
        }
        int m = map.size();
        if (n <= m)
        {
            res = n;
        }
        else
        {
            res = m;
        }
        return res;
    }
   
};

2.set容器

因为不考虑重复元素，可以直接存入set容器中，并且在插入set时进行了优化。因为map需要同时插入键值和键值对所以不能这样执行。

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