算法第二十九天-森林中的兔子
森林中的兔子
题目要求
解题思路
重点：某个兔子回答x的时候，那么数组中最多循序x+1个同花色的兔子同时回答x
我们可以通过举例子得出一下的规律：
我们统计数组中所有回答x的兔子的数量n：
- 若
n%(x+1)==0，说明我们此时只需要n/(x+1)种不同颜色的兔子，每种颜色兔子的个数为x+1; - 若
n%(x+1) !=0说明我们此时只需要n/(x+1)+1种不同颜色的兔子，每种颜色兔子的个数为x+1
那么通过这两种情况可以通过ceil(n/(x+1))来整合（其中国ceil()是向上取整函数），即n/(x+1)向下取整 种不同颜色的兔子
向上取整的函数可以自己实现也可以转化为(n+x)/(x+1)，这个公式中的除法是向下取整。
代码
class Solution:
def numRabbits(self, answers: List[int]) -> int:
count = collections.Counter(answers)
return sum((count[x] + x) // (x + 1) * (x + 1) for x in count)
复杂度分析
时间复杂度：
O
(
N
)
O(N)
O(N)
空间复杂度：
O
(
N
)
O(N)
O(N)