LeetCode演算法題-Distribute Candies（Java實現）
這是悅樂書的第266 次更新，第279 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第133題（順位題號是575）。給定具有偶數長度的整數陣列，其中該陣列中的不同數字表示不同種類的糖果。 每個數字表示相應種類的一種糖果。 您需要將這些糖果平均分配給哥哥妹妹。 返回妹妹可以獲得的最多種類數量的糖果。例如：
輸入：糖果= [1,1,2,2,3,3]
輸出：3
說明：有三種不同的糖果（1,2和3），每種糖果兩種。最佳分配：妹妹有糖果[1,2,3]，哥哥也有糖果[1,2,3]。妹妹有三種不同的糖果。
輸入：糖果= [1,1,2,3]
輸出：2
說明：例如，妹妹有糖果[2,3]，哥哥有糖果[1,1]。妹妹有兩種不同的糖果，兄弟只有一種糖果。
注意：
-
給定陣列的長度在[2,100]範圍內，並且是偶數。
-
給定陣列中的數字在 [-100000, 100000]範圍內。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
陣列長度是偶數，要將裡面的糖果平分給哥哥和妹妹，使得妹妹分到的糖果種類最多。妹妹要想分的糖果種類最多，分為三種情況：
第一，糖果種類和糖果數量的1/2相等，兩人分的種類一樣多。
第二，糖果種類大於糖果數量的1/2，妹妹得到的糖果種類，最多是糖果數量的1/2.
第三，糖果種類小於糖果數量的1/2，妹妹得到所有的種類。
所以，我們需要知道糖果種類和糖果數量的1/2之間的大小關係，就能直接得出妹妹可以得到的最大糖果種類。使用HashMap，以糖果種類為key，該種類的糖果數量為value，最後比較map的size與陣列長度的1/2之間的大小。
public int distributeCandies(int[] candies) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : candies) {
map.put(num, map.getOrDefault(num, 0)+1);
}
if (map.size() < candies.length/2) {
return map.size();
}
return candies.length/2;
}
03 第二種解法
其實我們並不需要知道每一個種類的糖果，它的數量有多少，我們只需要有多少種就行。所以，將第一種解法的HashMap替換成HashSet，同樣對其size與陣列長度的1/2比較大小。
public int distributeCandies2(int[] candies) {
Set<Integer> set = new HashSet<Integer>();
for (int num : candies) {
set.add(num);
}
if (set.size() < candies.length/2) {
return set.size();
}
return candies.length/2;
}
04 第三種解法
我們也可以直接遍歷陣列元素，來獲取其中的糖果種類，但是需要先排序，這樣才能保證種類記數是有效的。
public int distributeCandies3(int[] candies) {
Arrays.sort(candies);
int count = 1;
for (int i=1; i<candies.length; i++) {
if (candies[i-1] != candies[i]) {
count++;
}
}
if (count < candies.length/2) {
return count;
}
return candies.length/2;
}
05 第四種解法
我們也可以不使用排序，使用一個新的陣列，型別選擇為布林型別，此陣列初始化時，全部元素值都為false，長度為200001，因為candies的取值範圍是[-100000,100000]，以candies的元素值加上100000作為新陣列的索引，然後將新陣列中的元素值改為true，count加1，最後比較count和陣列長度的1/2的大小。
public int distributeCandies4(int[] candies) {
boolean[] temp = new boolean[200001];
int count = 0;
for (int num : candies) {
if (!temp[num+100000]) {
count++;
temp[num+100000] = true;
}
}
return count < candies.length/2 ? count : candies.length/2;
}
06 小結
演算法專題目前已日更超過四個月 ，演算法題文章133 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！