[LeetCode-575]分糖果

原题链接

题目描述

总共有偶数个数字, 从中选择一半的数字且数字的种类最多.

思路

• 贪心: 总共选的数字的个数是固定的, 对于每一种数字可以贪心的只选择一个, 这样后面可供选择的余地就越大.

Code

class Solution {
public:
    int distributeCandies(vector<int>& nums) {
        // 哈希表统计每个数字的个数
        unordered_map<int, int> mp;
        for (auto& num : nums)
            mp[num] ++ ;

        int s = nums.size() / 2;
        return min(s, (int)mp.size());
    }
};

---

复杂度分析

• 时间复杂度$O(n)$, 只需遍历数组统计类别
• 空间复杂度$O(n)$, 哈希表所需空间为$O(n)$

---

欢迎讨论指正