問題（Easy）：
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:
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:
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:
- The length of the given array is in range [2, 10,000], and will be even.
- The number in given array is in range [-100,000, 100,000].
大意：
給出一個偶數(shù)長度的證書數(shù)組，其中不同的數(shù)字表示不同類別的糖果。每個數(shù)字表示一個不同類別的糖果。你需要將這些糖果平均分給弟弟和妹妹。返回妹妹能得到的最大的糖果種類數(shù)。
例1：
輸入：candies = [1,1,2,2,3,3]
輸出：3
解釋：
有三種糖果（1，2，3），每種類別有兩個糖果。
可選的分布：妹妹得到糖果[1,2,3]，弟弟也得到通過[1,2,3]。
妹妹得到了三種糖果。例2：
輸入：candies = [1,1,2,3]
輸出：2
解釋：比如，妹妹得到糖果[2,3]，弟弟得到糖果[1,1]。
妹妹有兩種糖果，而弟弟只有一種。注意：
- 給出數(shù)組的長度在[2, 10000]，會是偶數(shù)。
- 給出的數(shù)字的范圍在[-100000, 100000]。
思路1：
其實就是看有多少個糖果種類，也就是多少個不同的數(shù)字，因為糖果一定是均分給兩人的，如果種類數(shù)大于總數(shù)的一半，那妹妹能得到的最大種類數(shù)就是總數(shù)的一半。如果種類數(shù)小于總數(shù)的一半，那肯定最多能得到的就是種類數(shù)了。
需要注意的是題目并沒說給出的數(shù)組是排了序的，所以不能直接遍歷看種類，需要用一些集合來記錄出現(xiàn)過的種類（數(shù)字），遇到出現(xiàn)過的就不再記錄了，遍歷一遍后得到總種類數(shù)，再跟總數(shù)的一半比大小就知道了。
代碼1（C++）：
class Solution {
public:
int distributeCandies(vector<int>& candies) {
int num = candies.size() / 2;
int sort = 0;
map<int, int> maps;
auto iter = candies.begin();
while (iter != candies.end()) {
if (maps.find(*iter) == maps.end()) {
sort++;
maps.insert(pair<int, int>(*iter, 1));
}
iter++;
}
if (sort > num) return num;
else return sort;
}
};
其實用set會更加方便一點，不用判斷是否出現(xiàn)過，直接放set里放，最后統(tǒng)計set里的元素數(shù)，set保證一樣的只會留一個。且最后的比較可以用min函數(shù)。
代碼1改進（C++）：
class Solution {
public:
int distributeCandies(vector<int>& candies) {
unordered_set<int> kinds;
for (int kind : candies) {
kinds.insert(kind);
}
return min(kinds.size(), candies.size() / 2);
}
};
思路2：
前面也說到了排序，如果先給集合排個序，那么就可以遍歷集合來統(tǒng)計種類數(shù)了，只要遍歷時跟前一個比較是否一樣即可，這種方式因為要事先排序，時間復雜度會降低為排序的時間復雜度。
代碼2（C++）：
class Solution {
public:
int distributeCandies(vector<int>& candies) {
size_t kinds = 0;
sort(candies.begin(), candies.end());
for (int i = 0; i < candies.size(); i++) {
kinds += i == 0 || candies[i] != candies[i - 1];
}
return min(kinds, candies.size() / 2);
}
};
合集：https://github.com/Cloudox/LeetCode-Record
