问题：
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: 3Explanation: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: 2Explanation: 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].
解决：
①使用HashMap对糖果进行分类，若糖果种类大于数组的一半，则sister最多得数组的一半的种类，否则，得到map中的分类数。耗时157ms。
public class Solution {
public int distributeCandies(int[] candies) {//妹妹最多能得多少中糖果 Map<Integer,Integer> map = new HashMap<>(); int n = candies.length; for (int i = 0;i < candies.length ;i ++ ) { map.put(candies[i],map.getOrDefault(candies[i],0) + 1); } if(map.size() > n / 2){//若糖果的种类大于数组的一半，最多得一半 return n / 2; }else{//否则，返回糖果的种类即可 return map.size(); } } }②使用了自己写的hash表来对糖果进行分类。耗时95ms。
public class Solution {
public int distributeCandies(int[] candies) {//妹妹最多能得多少中糖果 int[] hash = new int[200001];//用于存储种类 for (int i = 0;i < candies.length ;i ++ ) { hash[candies[i] + 100000] ++; } int count = 0; for (int arr:hash) { if(arr != 0){ count ++; } } if (count > candies.length / 2) { return candies.length / 2; }else{ return count; } } }public class Solution {
public int distributeCandies(int[] candies) {//这样处理性能会好一些 byte[] hash = new byte[200001]; int count = 0; int l = candies.length / 2; for (int i = 0; i < candies.length; i++) { if (hash[candies[i] + 100000] == 0) { hash[candies[i] + 100000] = 1; count ++; } if (count >= candies.length / 2){ return candies.length / 2; } } return count; } }③使用HashSet存储每一种类。耗时123ms。
public class Solution {
public int distributeCandies(int[] candies) { Set<Integer> set = new HashSet<>(); for (int c : candies) { set.add(c); } return set.size() > candies.length / 2 ? candies.length / 2 : set.size(); } }④也可以将数组先排序，然后进行遍历种类。耗时105ms。
public class Solution {
public int distributeCandies(int[] candies) {//这样处理性能会好一些 Arrays.sort(candies); int count = 1; for (int i = 1;i < candies.length;i ++) { if (candies[i] != candies[i - 1]) { count ++; } if (count > candies.length / 2) { return candies.length / 2; } } return count; } }