This is the 27th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021.

Title description:

575. Share candy – LeetCode (leetcode-cn.com)

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

The sample a

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 <= 10^4
  • nIt’s an even number
  • -10^5 <= candyType[i] <= 10^5

Thought analysis

greedy

Now see this kind of topic has been conditioned reflex, with greed.

Since the problem specifies an even number of sweets nn, it must be possible to divide the sweets equally into two pieces, each fixed at n2\frac{n}{2}2n.

If the number of confectionery types is mm, the maximum number of confectionery types in a single serving can be min(m,n2)min(m, \frac{n}{2})min(m,2n).

It might be a little abstract to say this directly, but let’s prove it separately:

If m≤n2m\le\dfrac{n}{2}m≤2n, then at least one of each kind of candy can be given to the sister, then the answer is m;

If m>n2m>\dfrac{n}{2}m>2n, the sister can only get n2\dfrac{n}{2}2n kinds of candy, one of each candy, then the answer is n2\dfrac{n}{2}2n.

Min (m,n2)min\Big(m,\dfrac{n}{2}\Big)min(m,2n).

AC code


class Solution {
    fun distributeCandies(candyType: IntArray): Int {
        val candyTypeSet = HashSet<Int> ()for (candy in candyType) {
            candyTypeSet.add(candy)
        }
        return minOf(candyType.size / 2, candyTypeSet.size)

    }
}
Copy the code

conclusion

The main thing is greedy understanding. If he doesn’t understand, see the reference links below for excellent answers.

reference

Divide the candy – Divide the candy – Force Buckle (LeetCode) (leetcode-cn.com)

[LeetCode](leetcode-cn.com)](leetcode-cn.com/problems/di…

【 Miyazui Triloba Believe science Series 】分 situation Discussion greedy proof – 分 candy – Force button (LeetCode) (leetcode-cn.com)