网络异常,图片无法展示
|
题目描述
这是 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)。
可以使用「分情况讨论」进行证明:
- m > \frac{n}{2}m>2n:糖果种类大于单份的糖果数量。此时可以从 mm 类糖果中找出 \frac{n}{2}2n 类不同的糖果组成单份,此时可取得的最大种类数量为 \frac{n}{2}2n;
- m = \frac{n}{2}m=2n:糖果种类等于单份的糖果数量。同理,此时可以从 mm 类糖果中找出 \frac{n}{2}2n 类不同的糖果组成单份,此时可取得的最大种类数量为 m = \frac{n}{2}m=2n;
- 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 原题链接和其他优选题解。