• This is the first day of my participation in the Gwen Challenge in November. Check out the details: the last Gwen Challenge in 2021

Leetcode – 575 – cent candy

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Github has not been updated. It is expected to be updated this weekend

[B].

Alice has n sugars, where the ith sugar is of candyType[I]. Alice noticed that she was gaining weight, so she went to visit a doctor.

Alice is advised to eat less sugar, just n / 2 of all the sugar she has (n is an even number). Alice liked them so much that she wanted to eat as many different types of sugar as possible, following her doctor’s advice.

CandyType = candyType = candyType = candyType = candyType = candyType = candyType = candyType

 

Example 1:

Input: candyType = [1,1,2,2,3,3] output: 3 explanation: Alice can only eat 6/2 = 3 sweets, and since there are only 3 sweets, she can eat one of each.Copy the code

Example 2:

Input: candyType = [1,1,2,3] output: 2 explanation: Alice can only eat 4/2 = 2 sweets, regardless of the type she chooses to eat [1,2], [1,3] or [2,3], she can only eat two different types of sugar.Copy the code

Example 3:

Input: candyType = [6,6,6,6] output: 1 explanation: Alice can only eat 4/2 = 2 candies, and although she can eat 2 candies, she can only eat 1 candy.Copy the code

Tip:

  • n == candyType.length
  • 2 <= n <=
    1 0 4 10^4
  • N is an even number

  • − 1 0 5 -10^5     <= candyType[i] <=
    1 0 5 10^5

Idea 1: Greedy method

  • It’s time for simple problems and complex analysis
  • Once I saw a sentence in the group, which should be the general y said, all the proof of greedy method is too strong, or too weak
  • And, of course, I think the other way of writing a very detailed proof is in two ways, mitsuha’s kind and my kind
  • It’s easy to think of the greedy method, so let’s start the proof process
  • Let’s first define the number of species as a, and there must be n over 2 given to Alice because the length is N
  • When n/2<= A, the candy of type N /2 must be distributed to Alice
  • When a
  • At the same time, a candy is given to Alice in each category
  • So res= math.min (a,n/2);
class Solution {
    public int distributeCandies(int[] candyType) {
        int max = 0, type = candyType.length;
        Set<Integer> set = new HashSet<>();
        for(int candy: candyType){
            if(!set.contains(candy)){
                max++;
                set.add(candy);
            }
        
        }
        int n = type /2;
        if(max >= n){
            return n;
        }
        returnmax; }}Copy the code
  • Time complexity O(n)
  • Space complexity O(n)