🔗 🟢 575. Distribute Candies

tags: `貪心(Greedy)` `集合(Set)`

題意

給定一個長度為 $n$ 的整數陣列 $candyType$ ，表示每個糖果的類型。Alice 想要在吃掉 $n / 2$ 顆糖果的情況下，吃到最多不同種類的糖果。

返回 Alice 在只吃掉 $n / 2$ 顆糖果的情況下，可以吃到糖的最多種類數， $n$ 為偶數。

思路：貪心(Greedy) + 集合(Set)

若糖果種類數量為 $k$ ，考慮以下兩種情況：

$k > \frac{n}{2}$ ，由於 Alice 最多只能吃 $n / 2$ 種糖果，因此能吃到的最多種類數即為 $\frac{n}{2}$ 。
$k \leq \frac{n}{2}$ ，則 Alice 最多能吃到 $k$ 種糖果。

故答案為 $\min(k, \frac{n}{2})$ ，其中 $k$ 為糖果種類數量，可以使用 set 來計算。

複雜度分析

時間複雜度： $O(n)$
空間複雜度： $O(n)$

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        # return min(len(candyType)//2, len(set(candyType)))
        n = len(candyType)
        st = set(candyType)
        return min(n//2, len(st))

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