一【題目類別】

• 哈希表

二【題目難度】

• 簡單

三【題目編號】

• 575.分糖果

四【題目描述】

• Alice 有 n 枚糖，其中第 i 枚糖的類型為 candyType[i] 。Alice 注意到她的體重正在增長，所以前去拜訪了一位醫(yī)生。
• 醫(yī)生建議 Alice 要少攝入糖分，只吃掉她所有糖的 n / 2 即可（n 是一個偶數(shù)）。Alice 非常喜歡這些糖，她想要在遵循醫(yī)生建議的情況下，盡可能吃到最多不同種類的糖。
• 給你一個長度為 n 的整數(shù)數(shù)組 candyType ，返回： Alice 在僅吃掉 n / 2 枚糖的情況下，可以吃到糖的 最多 種類數(shù)。

五【題目示例】

• 示例 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.length$
• $2<=n<=10^4$
• $n是一個偶數(shù)$
• $?10^5<=candyType[i]<=10^5$

七【解題思路】

• 因為糖果的個數(shù)總共為$n$個，所以根據(jù)題意，最后返回的結(jié)果不會超過$\frac{n}{2}$
• 此外，設(shè)這些糖果一共有$m$種，所以說返回的結(jié)果也不會超過$m$
• 如果$m\le \frac{n}{2}$，那么說明可以吃到重復(fù)的糖果，但是最多吃到$m$種糖果，返回的結(jié)果就是$m$
• 如果$m\ge \frac{n}{2}$，那么說明就算有再多的糖果種類，也只能吃到$\frac{n}{2}$顆糖果
• 綜上所述，最后返回的結(jié)果為：$min(m,\frac{n}{2})$
• 實現(xiàn)以上思路使用哈希表即可，比較簡單，具體內(nèi)容可參見下面的代碼
• 最后返回結(jié)果即可

八【時間頻度】

• 時間復(fù)雜度：$O(n)$，$n$為傳入的數(shù)組的長度
• 空間復(fù)雜度：$O(n)$，$n$為傳入的數(shù)組的長度

九【代碼實現(xiàn)】

1. Java語言版

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

2. C語言版

int distributeCandies(int* candyType, int candyTypeSize)
{
    int* map = (int*)calloc(200001, sizeof(int));
    for(int i = 0;i < candyTypeSize;i++)
    {
        map[candyType[i] + 100000]++;
    }
    int count = 0;
    for(int i = 0;i < 200001;i++)
    {
        if(map[i] > 0)
        {
            count++;
        }
    }
    return fmin(count, candyTypeSize / 2);
}

3. Python語言版

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

4. C++語言版

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

十【提交結(jié)果】

1. Java語言版
   

2. C語言版
   

3. Python語言版
   

4. C++語言版
   文章來源地址http://www.zghlxwxcb.cn/news/detail-636670.html

到了這里，關(guān)于【LeetCode每日一題】——575.分糖果的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！