“This is the first day of my participation in the Gwen Challenge in November. See details of the event: The last Gwen Challenge in 2021”.

Topic describes

This is 575 on LeetCode. Divide the candy. The difficulty is easy.

Tag: “Greedy.”

Given an even-length array in which different numbers represent different types of candy, each number represents a candy. You need to divide the candy equally between one brother and one sister.

Returns the maximum number of types of candy your sister can get.

Example 1:

[1,1,2,2,3] there are two of each kind of candies Optimal allocation: younger sister gets [1,2,3], younger brother also gets [1,2,3]. This gives her the most variety of sweets.Copy the code

Example 2:

Sister has two different kinds of candies, the brother has only one This maximizes the number of sweets available to the younger sister.Copy the code

Note:

  • The array has a length of [2, 10,000] and is determined to be even.
  • The numbers in the array are in the range [-100,000, 100,000].

greedy

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

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

You can use “case by case discussion” to prove:

  1. M >n2m > \frac{n}{2}m>2n: The type of candy is greater than the number of candy in a single serving. At this point, n2\frac{n}{2}2n types of sweets can be found from the MMM type of sweets, and the maximum number of types available is n2\frac{n}{2}2n.

  2. M =n2m = \frac{n}{2}m=2n: The type of candy is equal to the number of candies in a single serving. In the same way, different types of n2\frac{n}{2}2n can be found from the MMM candy. The maximum number of types available is m=n2m = \frac{n}{2}m=2n.

  3. M

In conclusion, regardless of the relationship between the number of candy types and the number of candies per serving, the maximum number of candy types we can obtain is min⁡(m,n2)\min(m, \frac{n}{2})min(m,2n).

Code:

class Solution {
    public int distributeCandies(int[] candyType) {
        Set<Integer> set = new HashSet<>();
        for (int i : candyType) set.add(i);
        return Math.min(candyType.length / 2, set.size()); }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

The last

This is the No.575 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks, we will first finish all the topics without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.