题目链接:. - 力扣(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定义成全局变量,调试了很长时间,都过不去,就是找不到问题在哪,一定要记住这个坑呀!(当然,不亲身经历应该是记不住的,希望你们经历后,再来看这段话是什么感受)