当前位置：网站首页>781. 森林中的兔子

781. 森林中的兔子

2022-08-09 22:41:00 【InfoQ】

781. 森林中的兔子

森林中有未知数量的兔子。提问其中若干只兔子 "还有多少只兔子与你（指被提问的兔子）颜色相同?" ，将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。

给你数组 answers ，返回森林中兔子的最少数量。

来源：力扣（LeetCode）

链接：

https://leetcode.cn/problems/rabbits-in-forest

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

给兔子分组

先排序,让相同的兔子在一起

这样就可以让相同的兔子分组,组内自我消化

排序好了,我们要怎么计算出相同的兔子的数量呢,

我们发现第一种颜色有4只兔子的回答为1

那么在第一种颜色中可以分为2只兔子为一组

因为1代表这除了自己还有另外一只兔子颜色相同

因此2只兔子为一组,因此第一种颜色的兔子有4只

到了第2种颜色

2代表着除了自己还有2只兔子颜色相同

因此需要分成3只兔子为一组

但第二种颜色的兔子在数组中只有2只,无法凑齐3只

证明还有兔子没被调查,需要在额外补一只兔子,

因此第二种颜色的兔子数量为3

同理可得,第三种颜色的兔子有8只

第四种颜色的兔子有5只,因为数组中只有3只,需要另外补2只,

第五种颜色的兔子有6只

计算公式

变量x代表有多少只兔子颜色相同

c代表当前颜色的兔子在数组中有多少只

如果当前数是x,有c只，有几组?

我们以7个3为例子

3代表除了自己有3只兔子颜色相同

因此4只兔子为一组

我们需要分出2组

因此为7/4向上取整

那么怎么向上取整

原本是a/b

向上取整变为

(a+(b-1))/b

因此最后公式为((c+x)/(x+1))*(x+1),

代码

class Solution {
 public int numRabbits(int[] answers) {
 int n=answers.length;
 if(answers==null||n==0){
 return 0;
 }
 Arrays.sort(answers);
 int x=answers[0];
 int c=1;
 int ans=0;
 for(int i=1;i<n;i++){
 if(x!=answers[i]){
 ans+=((c+x)/(x+1))*(x+1);
 x=answers[i];
 c=1;
 }else{
 c++;
 }
 }
 return ans+((c+x)/(x+1))*(x+1);
 }
}