LeetCode – 575. Distribute Candies

題目來源:LeetCode – 575. Distribute Candies


題目:

Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.

Example 1:

Example 2:

Note:

  1. The length of the given array is in range [2, 10,000], and will be even.
  2. The number in given array is in range [-100,000, 100,000].

粗略翻譯:

題目會給予一組長度均勻的陣列,陣列中的不同數字代表不同種類的糖果,

每個數字也代表對應種類的一顆糖果,程式的目的是要平均的分配陣列中的糖果給哥哥跟姊姊

但要盡可能地讓姊姊拿到最多種類的糖果,並輸出姊姊拿到糖果種類的數量。

例如陣列是 [1,1,2,2,3,3] ,代表糖果的種類有1, 2, 3,

而哥哥跟姊姊都可以拿到[1, 2, 3]各一顆的糖果,因此輸出3。

如果陣列是[1,1,2,3],代表糖果種類有1, 2, 3,

為了讓姊姊拿到最多種類的糖果,因此哥哥拿[1, 1],姊姊拿[2, 3]

因此輸出2。

解法:

由於程式目的是要讓姊姊拿到最多種類的糖果

所以我們只需在乎糖果的種類有幾種,不需要知道該種類有幾顆

因此用Set來實作,先將candies全部add到kinds裡

而回傳時需要判斷一下kinds的數量是否大於candies / 2的數量

如果成立,代表種類多於總數量除2,那我們就回傳candies / 2即可。

如果不成立,代表種類少於總數量除2,但為了讓姊姊拿到最多的種類,

因此回傳kinds的size即可。


網站:http://wp.mlab.tw/
GitHub:https://github.com/yoll522/LeetCode
程式碼:https://github.com/yoll522/LeetCode/tree/master/575.%20Distribute%20Candies

6 comments

Leave a Reply

你的電子郵件位址並不會被公開。 必要欄位標記為 *