LeetCode575——分糖果

     题目链接：. - 力扣（LeetCode）

        这道题比较简单，但我还是花费了将近四个小时的时间去解答，AC的那一刻，终于全身舒畅，这道题的思路就是先求出糖果的种数，然后我们从题中可以得出，Alice最少吃一种糖果，最多吃n/2种糖果,我们可以用二分法来写，下面来看代码：

//求出糖果种数，哈希的方式
int typecount(int* a, int size)
{
    //开辟空间注意数据范围，题上给的a[i]的数据范围是-100000到100000
    int* hx = calloc(200010,sizeof(int));//calloc开辟出来的空间初始都为0
    int count = 0;
    for (int i = 0; i < size; i++)
    {
        hx[a[i]+100000]++;//因为题上给的a[i]的数据范围是-100000到100000，所以
    }                     //hx[a[i]+100000]可以避免数组下标是负数
    for (int i = 0; i < 200010; i++)
    {
        if (hx[i] != 0)//ha[i]不为0，就说明是一种糖果类型,count++
        {
            count++;
        }
    }
    free(hx);//释放calloc开辟的空间
    return count;
}

int check(int mid,int count)
{
    if (mid < count)
        return 1;
    return 0;
}

int distributeCandies(int* candyType, int candyTypeSize) {
    int n = candyTypeSize;
    
    int count=typecount(candyType, candyTypeSize);//糖果种类
    //因为Alice最少吃一种糖果，最多吃n/2种糖果，所以用二分法
    int l = 1, r = n / 2;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(mid,count))
        {
            l = mid + 1;//如果mid<count，更新左边界，l=mid+1，因为mid肯定不是我们要找的值，
                        //所以我们在[mid+1,r]这个区间去找
        }
        else
            r = mid;//如果mid>=count，更新右边界，r=mid，因为mid可能等于count，也就是说
                    //mid可能是我们要找的值，所以我们在[l,mid]这个区间找
    }
    return r;//最后返回r就是Alice吃到糖的最多种类数,其实返回l也是可以的，因为到
            //最后l==r，返回哪个都是可以的
}

       代码注释的很清楚，这里就不再细说了，还需要注意的一点是count可能大于n/2，但是不影响，我们只需要在[1,n/2]这个区间找就好了。

        请注意 :轻易不要定义全局变量，很危险的，我就是因为把hx定义成全局变量，调试了很长时间，都过不去，就是找不到问题在哪，一定要记住这个坑呀！（当然，不亲身经历应该是记不住的，希望你们经历后，再来看这段话是什么感受）