0575. Distribute Candies (Easy)

Question

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

1
2
3
4
5
6

Input: candies = [1,1,2,2,3,3]
Output: 3
Explanation:
There are three different kinds of candies (1, 2 and 3), and two candies for each kind.
Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too.
The sister has three different kinds of candies.

Example 2

1
2
3
4

Input: candies = [1,1,2,3]
Output: 2
Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1].
The sister has two different kinds of candies, the brother has only one kind of candies.

Note:

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

分析/解題

給定一個偶數長度的整數陣列，當中不同的數字代表不同種類的糖果。
你要將糖果平分給一對兄妹(姐弟)，試算出當中姐姐/妹妹最多能拿到幾種不同種類的糖果。

什麼？題目也偏女生嗎(大誤)

題目內文基本上已經講得相當清楚了，
接下來問題就來到究竟我們要怎麼知道種類有多少種不同呢？
首先，如果每顆糖果都不同種類，女生最多能拿的也只有一半 ，
所以能拿到的種類上限會受限於candies的總數除以2 。
這個是大前提，我們先將它放在一邊。

那麼，如果種類總數比candies總數的一半小 呢？
簡單的想法就是發糖果的時候，每次遇到沒看過的種類，
就先記起來，藉此將整個種類數計數過一遍。
(或者你也可以想成每次看到沒看過的種類 要優先給女生，
給到女生拿滿 或沒有新的種類 為止，兩個思考的模式和條件其實差不多。)

要記錄某種糖果的出現數量，
自然會想到HashTable/HashSet/Dictionary這類的東西，
但由於題目有提到種類是從-100000~100000，
所以其實我們可以開出一個長度為200001的陣列/串列，
直接當成Hash Table來使用，只要位移個100000即可。
(陣列/串列要從0開始)

因此，我們每次就可以從candies中依序取出一個數字，
將Hash Table內的對應位置進行遞增，再看看加完後是否剛好是1，
是1就代表這是新種類的糖果，所以要將種類的變數加1。

最後再回頭比較種類的數量，跟糖果的總數的一半，
選擇較小的進行回傳即可。

依此，寫成程式碼：

Java

Python的部分，我們也可以用set的方式取得不重複的種類，
再取其len()即可得到不重複的種類數量。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(N)，如果將空間固定成題目給定的限制的話，
會固定要開出一個200001的空間，這個可以再直接用說的。)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VE9Q5VE**