写点什么

781. 森林中的兔子

作者:Geek_f891fd
  • 2022 年 8 月 09 日
    广东
  • 本文字数:871 字

    阅读完需:约 3 分钟

781. 森林中的兔子

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);    }}
复制代码


用户头像

Geek_f891fd

关注

还未添加个人签名 2022.08.04 加入

还未添加个人简介

评论

发布
暂无评论
781. 森林中的兔子_力扣_Geek_f891fd_InfoQ写作社区