Day575: divide candy

problem ： Divide candy

Given an even length array , Different numbers represent different kinds of candy , Each number represents a candy . You need to divide the candy equally between a younger brother and a younger sister . Return the maximum number of sweets sister can get .

Example 1:
Input : candies = [1,1,2,2,3,3]
Output : 3
analysis : There are three kinds of candy , Each has two .
Optimal allocation scheme ： Sister get [1,2,3], My brother also got [1,2,3]. In this way, my sister can get the most kinds of candy .

Example 2 :
Input : candies = [1,1,2,3]
Output : 2
analysis : My sister gets candy [2,3], My brother gets candy [1,1], Sister has two different kinds of candy , There is only one kind of brother . In this way, my sister can get the most kinds of candy .

source ： Power button （LeetCode）

Train of thought ： aggregate （set)

1. If the type of candy is greater than n/2,n Is the total number of sweets , Sister can get at most n/2 Grow candy .
2. If the candy type is m,m<n/2, Sister can get at most m Grow candy .
3. It can be obtained. , The maximum number of sweets my sister can get is min(m,n/2).

class Solution {
    
    public int distributeCandies(int[] candyType) {
    
        Set<Integer> candyTypeSet = new HashSet<Integer>();
        for(int candy : candyType){
    
            candyTypeSet.add(candy);
        }
        return Math.min(candyTypeSet.size(),candyType.length/2);
    }
}

Train of thought two ： Sort

1. Sort the array ;
2. Find out how many kinds of candy there are in the array ;
3. Returns half the length of the array and the minimum value in the candy category .

class Solution {
    
    public int distributeCandies(int[] candyType) {
    
        Arrays.sort(candyType);
        int count = 1;
        for(int i=1; i<candyType.length; i++){
    
            if(candyType[i]>candyType[i-1])
                count += 1;
        }
        return Math.min(count,candyType.length/2);
    }
}