三分钟看完「分糖果」算法问题

一时失言乱红尘 2022-02-03 13:51 384阅读 0赞

题目来源于 LeetCode 上第 575 号问题：分糖果。题目难度为 Easy，目前通过率为 60.2% 。

### 题目描述 ###

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

**示例 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\]，妹妹有两种不同的糖果，弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。

**注意:**

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

### 题目解析 ###

总共有 n 个糖，平均分给两个人，每人得到 n／2 块糖，那么能拿到的最大的糖的种类数也就是 n／2 种，不可能更多，只可能更少。

所以只需要统计出糖的种类数，如果糖的种类数小于 n／2，说明拿不到 n／2种糖，最多能拿到的种类数就是当前糖的总种类数。最后，看（数量的一半）和（所有的种类）哪个先达到，取两者中较小的值即可。

举个例子：

*  极端情况1：所有糖都不重样，这种情况妹妹也只能拿到一半的糖果。
 *  极端情况2：只有一种糖，这种情况妹妹只能得到一种糖果。
 *  平均情况：每个糖都有两个，这种情况妹妹可以拿到所有种类，数量与 **极端情况1** 一样。

求糖果的种类数使用 hash 即可。

### 图片描述 ###

![640?wx\_fmt=png][640_wx_fmt_png]

### 代码实现 ###

class Solution\{  
public int distributeCandies(int\[\] candies)\{  
Set<Integer> nums = new HashSet<>();  
for (int i = 0; i < candies.length; i++) \{  
nums.add(candies\[i\]);  
\}  
int numNums = nums.size();  
int numTarget = candies.length / 2;  
return numNums >= numTarget ? numTarget : numNums;  
\}  
\}

**往期热文**

[拜托，面试官别问我「布隆」了][Link 1]

[有点难度，几道和「滑动窗口」有关的算法面试题][Link 2]

**推****荐阅读**

[几道和「二叉树」有关的算法面试题][Link 3]  
[几道和「堆栈、队列」有关的面试算法题][Link 4]

[链表算法面试问题？看我就够了！][Link 5]

[一道看完答案你会觉得很沙雕的「动态规划算法题」][Link 6]

[如何有效的写算法题][Link 7]

来和程序员小吴一起学算法~

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

我就知道你在看！

[640_wx_fmt_png]: /images/20220203/f3f29e8c7fd94f48b335805212ebe4d8.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485011&idx=1&sn=a3031a3d3ad033e44439d42d72753e16&chksm=fa0e69d2cd79e0c45b1eb017c65b60662890f67ec70ef44e92ef7f5cddfc313ea6ab353952f4&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485197&idx=1&sn=1bbd40d49adb09875fd324664bd5bc8b&chksm=fa0e688ccd79e19a36599b53e4a8acf9a725ace3f6df28925075ff25778238471a283f0f8e1f&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484985&idx=1&sn=93343d355abf36c77a361c9931cbe2d1&chksm=fa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[Link 7]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485214&idx=1&sn=00de6e810caa7e261b8f2e19c3acd9cd&chksm=fa0e689fcd79e189282babbe3a688158b505e7b907971eede501addac9e0bec1e9d1c77ffb78&scene=21#wechat_redirect
[640_wx_fmt_jpeg]: /images/20220203/f3288fd72c74460ab47bacacfec20431.png