Li Kou daily question - day 29 -575 Divide candy

2022.6.27 Did you brush the questions today ？

---

subject ：

Alice Yes n Piece sugar , Among them the first i The type of sugar is candyType[i] .Alice Notice that she's gaining weight , So I went to visit a doctor .

The doctor suggested Alice Eat less sugar , Just eat all her sugar n / 2 that will do （n It's an even number ）.Alice I like these sweets very much , She wants to follow the doctor's advice , Eat as many different kinds of sugar as possible .

Give you a length of n Array of integers for candyType , return ： Alice Eat only n / 2 In the case of sugar , You can eat sugar most Number of species .

analysis ：

Give you an even array , You need to find a value that is half the size of the array x, And the types of different elements y Compare , If x Greater than or equal to y, Then return to y, Otherwise return to x.

Ideas ： We make use of map Container inserts elements , And then according to map The result can be obtained by comparing the size of the array with half the size of the original array

analysis ：

1. Hashtable

class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        unordered_map<int, int>map;
        int n = candyType.size() / 2;
        int res = 0;
        for (auto num : candyType)
        {
            map[num]++;
        }
        int m = map.size();
        if (n <= m)
        {
            res = n;
        }
        else
        {
            res = m;
        }
        return res;
    }
   
};

2.set Containers

Because we don't consider repeating elements , You can deposit it directly set In the container , And insert set Optimized for . because map You need to insert a key value and a key value pair at the same time, so you can't do this .

class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        unordered_set<int>set(candyType.begin(), candyType.end());
        int s = set.size();
        int res = min(s, (int)candyType.size() / 2);
    }
};