# 0575. 分糖果 ## 題目地址(575. 分糖果) <https://leetcode-cn.com/problems/distribute-candies/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個偶數長度的數組，其中不同的數字代表著不同種類的糖果，每一個數字代表一個糖果。你需要把這些糖果平均分給一個弟弟和一個妹妹。返回妹妹可以獲得的最大糖果的種類數。 示例 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]內。 ``` ``` ## 前置知識 - [數組](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) ## 公司 - 阿里 - 字節 ## 思路 由于糖果是偶數，并且我們只需要做到兩個人糖果數量一樣即可。 考慮兩種情況:  - 如果糖果種類大于n / 2（糖果種類數為n），妹妹最多可以獲得的糖果種類應該是`n / 2`(因為妹妹只有n / 2個糖). - 糖果種類數小于n / 2, 妹妹能夠得到的糖果種類可以是糖果的種類數（糖果種類本身就這么多）. 因此我們發現，妹妹能夠獲得的糖果種類的制約因素其實是糖果種類數。 ## 關鍵點解析 - 這是一道邏輯題目，因此如果邏輯分析清楚了，代碼是自然而然的 ## 代碼 - 語言支持：JS, Python Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=575 lang=javascript * * [575] Distribute Candies */</span> <span class="hljs-title">/** * @param {number[]} candies * @return {number} */</span> <span class="hljs-keyword">var</span> distributeCandies = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">candies</span>) </span>{ <span class="hljs-keyword">const</span> count = <span class="hljs-keyword">new</span> <span class="hljs-params">Set</span>(candies); <span class="hljs-keyword">return</span> <span class="hljs-params">Math</span>.min(count.size, candies.length >> <span class="hljs-params">1</span>); }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">distributeCandies</span><span class="hljs-params">(self, candies: List[int])</span> -> int:</span> <span class="hljs-keyword">return</span> min(len(set(candies)), len(candies) >> <span class="hljs-params">1</span>) ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經37K star啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。