What is the core trick in Rabbits in Forest?

The core trick is that each reply x represents a full color class of size x + 1. After counting how many times x appears, you round that count up into groups of size x + 1 instead of adding the replies directly.

Why does answers = [1,1,2] produce 5?

The two rabbits who said 1 can be one color group of size 2. The rabbit who said 2 must belong to a separate color group of size 3, which means two additional unseen rabbits are required, giving 2 + 3 = 5.

Why use a hash map for this pattern?

The array scanning plus hash lookup pattern works because only the frequency of each answer matters. Once you know how many times each x appears, the minimum contribution for that bucket is determined by the group-size formula.

Can I sort instead of using a hash table?

Yes, sorting also lets you process equal answers together, but it changes the time cost to O(n log n). The hash-map version is usually preferred in interviews because Rabbits in Forest only needs frequencies, not order.

What happens when a rabbit answers 0?

An answer of 0 means that rabbit's color group has size 1, so it contributes exactly one rabbit. Multiple zeros do not merge, because each zero describes a rabbit with no same-color partners.

#781

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

森林中的兔子

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

数组哈希表数学贪心

题目描述

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

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

示例 1：

输入：answers = [1,1,2]
输出：5
解释：
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。 
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。 
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。 
因此森林中兔子的最少数量是 5 只：3 只回答的和 2 只没有回答的。

示例 2：

输入：answers = [10,10,10]
输出：11

提示：

1 <= answers.length <= 1000
0 <= answers[i] < 1000

lightbulb

解题思路

方法一：贪心 + 哈希表

根据题目描述，回答相同的兔子，可能属于同一种颜色，而回答不同的兔子，不可能属于同一种颜色。

因此，我们用一个哈希表 $\textit{cnt}$ 记录每种回答出现的次数。对于每种回答 $x$ 及其出现次数 $v$ ，我们按照每种颜色有 $x + 1$ 只兔子的原则，计算出兔子的最少数量，并将其加入答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{answers}$ 的长度。

1

2

3

4

5

6

7

8

9

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        cnt = Counter(answers)
        ans = 0
        for x, v in cnt.items():
            group = x + 1
            ans += (v + group - 1) // group * group
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The interviewer expects you to notice that an answer x defines a group size of x + 1, not just x matching rabbits.
question_mark
They want a greedy counting argument showing why partially filled groups still force the full group cost.
question_mark
They are checking whether you reach for a hash map quickly instead of trying to simulate rabbit colors explicitly.

warning

常见陷阱

外企场景

error
Adding the frequency count directly and forgetting the hidden rabbits needed to complete a color group.
error
Treating every repeated answer as one shared group even when the count exceeds x + 1 and must spill into another group.
error
Mixing up x with x + 1, which breaks both the grouping formula and the example [1,1,2].

swap_horiz

进阶变体

外企场景

arrow_right_alt
Ask for the maximum possible rabbits instead of the minimum, which removes the tight greedy packing used in Rabbits in Forest.
arrow_right_alt
Stream the answers one by one and maintain the same grouped counting logic online with incremental frequencies.
arrow_right_alt
Return the number of color groups as well as the minimum rabbit count, using the same ceil(c / (x + 1)) computation per answer.

help

常见问题

外企场景

继续练习

#840 矩阵中的幻方 #846 一手顺子 #710 黑名单中的随机数