【刷穿 LeetCode】575. 分糖果 : 分情况讨论贪心证明题

题目描述

这是 LeetCode 上的 575. 分糖果 ，难度为 简单。

Tag : 「贪心」

给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。

返回妹妹可以获得的最大糖果的种类数。

示例 1:

输入: candies = [1,1,2,2,3,3]
输出: 3
解析: 一共有三种种类的糖果，每一种都有两个。
     最优分配方案：妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。
复制代码

示例 2 :

输入: candies = [1,1,2,3]
输出: 2
解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1]，妹妹有两种不同的糖果，弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。
复制代码

注意:

• 数组的长度为[2, 10,000]，并且确定为偶数。
• 数组中数字的大小在范围[-100,000, 100,000]内。

贪心

由于题目规定糖果数量 nn 为偶数，因此一定能将糖果平均分配成两份，每份数量固定为 \frac{n}{2}2n。

假设糖果种类数量为 mm，那么单份中可使得糖果种类数量最大为 \min(m, \frac{n}{2})min(m,2n)。

可以使用「分情况讨论」进行证明：

1. m > \frac{n}{2}m>2n：糖果种类大于单份的糖果数量。此时可以从 mm 类糖果中找出 \frac{n}{2}2n 类不同的糖果组成单份，此时可取得的最大种类数量为 \frac{n}{2}2n；
   
2. m = \frac{n}{2}m=2n：糖果种类等于单份的糖果数量。同理，此时可以从 mm 类糖果中找出 \frac{n}{2}2n 类不同的糖果组成单份，此时可取得的最大种类数量为 m = \frac{n}{2}m=2n；
   
3. m < \frac{n}{2}m<2n：糖果种类小于单份的糖果数量。此时先从 mm 类糖果中找出 mm 类不同糖果组成单份，再使用相同种类的糖果凑齐 \frac{n}{2}2n，此时可取得的最大种类数量为 mm。
   

综上，无论糖果种类数与单份糖果数呈何种关系，我们可取得的最大糖果种类数量均为 \min(m, \frac{n}{2})min(m,2n)。

代码：

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

• 时间复杂度：O(n)O(n)
• 空间复杂度：O(n)O(n)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.575 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。