哈希表 分糖果

題目

難度：簡(jiǎn)單

給定一個(gè)偶數(shù)長(zhǎng)度的數(shù)組，其中不同的數(shù)字代表著不同種類的糖果，每一個(gè)數(shù)字代表一個(gè)糖果。你需要把這些糖果平均分給一個(gè)弟弟和一個(gè)妹妹。返回妹妹可以獲得的最大糖果的種類數(shù)。

示例 1:

輸入: candies = [1,1,2,2,3,3] 輸出: 3 解析: 一共有三種種類的糖果，每一種都有兩個(gè)。 最優(yōu)分配方案：妹妹獲得[1,2,3],弟弟也獲得[1,2,3]。這樣使妹妹獲得糖果的種類數(shù)最多。

示例 2 :

輸入: candies = [1,1,2,3] 輸出: 2 解析: 妹妹獲得糖果[2,3],弟弟獲得糖果[1,1]，妹妹有兩種不同的糖果，弟弟只有一種。這樣使得妹妹可以獲得的糖果種類數(shù)最多。

注意:

數(shù)組的長(zhǎng)度為[2, 10,000]，并且確定為偶數(shù)。 數(shù)組中數(shù)字的大小在范圍[-100,000, 100,000]內(nèi)。

解法一、利用HashSet的特點(diǎn)

不可重復(fù)插入，于是依次插入，尋找共有最大幾個(gè)不同元素，與length/2，求最小

class Solution {
    public int distributeCandies(int[] candies) {
        HashSet <Integer> set = new HashSet < > ();
        for (int candy : candies){
            set.add(candy);
        }
        return Math.min(set.size(),candies.length/2);
    }
}

時(shí)間復(fù)雜度：O(n)。整個(gè)candiescandiescandies 數(shù)組只遍歷一次。這里，n表示 candies 數(shù)組的大小。 空間復(fù)雜度：O(n),在最壞的情況下，set 的大小為 n。

同理在Python中

class Solution:
    def distributeCandies(self, candies: List[int]) -> int:
        return len(set(candies)) if len(set(candies))<=len(candies)//2 else len(candies)//2