575. 分糖果

image-20211101124624197

解题思路：

​ 这题比较简单，一共有两种解题思路。

  • 用hash表记录下当前糖果种类，在其与平均分数目之间取最小值
  • 模拟整个分配过程，现将第一个分给妹妹，后续用leftCount记录下剩余可以分配的数量，并且在排序后通过candyType[i]>candyType[i-1]判断是否是新种类

以下是C++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        //方法1：
        //用hash表记录下当前糖果种类
        // unordered_map<int,int> m;
        // for(auto type:candyType){
        //     ++m[type];
        // }

        // int type_count=0;
        // for(auto pair:m){
        //     ++type_count;
        // }
        
        // return min(type_count,(int)candyType.size()/2);

        //方法2
        //模拟整个分配过程
        int length=candyType.size();
        int leftCount=length/2-1;
        int maxType=1;//现将第一个分给妹妹
        sort(candyType.begin(),candyType.end());
        for(int i=1;i<length&&leftCount>0;i++){
            if(candyType[i]>candyType[i-1]){
                leftCount--;
                maxType++;
            }
        }
        return maxType;
    }
};