各位题友大家好！今天是 @负雪明烛 坚持日更的第 70 天。今天力扣上的每日一题是「781. 森林中的兔子」。

解题思路

重点：当某个兔子回答 x 的时候，那么数组中最多允许 x+1 个同花色的兔子🐰同时回答 x。

我们先举个例子进行理解：
- 比如有一个红色的兔子回答了 2，那么数组中最多有 3 个红色的兔子。
- 如果数组是 [2,2,2] ，那么至少有一种颜色的兔子。
- 如果数组是 [2,2,2,2] ，那么说明至少有两种颜色的兔子，比如说前 3 个兔子构成一种颜色；那么最后一个兔子说的必须是其他颜色。
- 如果数组是 [2,2,2,2,2,2] ，那么说明至少有两种颜色的兔子，比如说前 3 个兔子构成一种颜色；那么后 3 个兔子说的必须是其他颜色。

通过上面的这个例子可以得出以下的规律。

我们统计数组中所有回答 $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)$，这个公式中的除法是向下取整。证明在代码后面。

我们还把上面的例子拿来，看一下计算的对不对。
- 如果数组是 [2,2,2] ，那么有 $ceil(n/(x+1)) = ceil(3/3) = 1$ 种颜色的兔子，也可以通过 $(n + x) / (x + 1) = (3 + 2) / (2 + 1) = 1$ 计算得到。
- 如果数组是 [2,2,2,2] ，那么有 $ceil(n/(x+1)) = ceil(4/3) = 2$ 种颜色的兔子，也可以通过 $(n + x) / (x + 1) = (4 + 2) / (2 + 1) = 2$ 计算得到。
- 如果数组是 [2,2,2,2,2,2] ，那么有 $ceil(n/(x+1)) = ceil(6/3) = 2$ 种颜色的兔子，也可以通过 $(n + x) / (x + 1) = (6 + 2) / (2 + 1) = 2$ 计算得到。

代码如下。

class Solution(object):
    def numRabbits(self, answers):
        count = collections.Counter(answers)
        return sum((count[x] + x) / (x + 1) * (x + 1) for x in count)

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        int res = 0;
        unordered_map<int, int> m;
        for (int a : answers) m[a]++;
        for (auto a : m) {
            res += (a.second + a.first) / (a.first + 1) * (a.first + 1);
        }
        return res;
    }
};

时间复杂度：$O(N)$
空间复杂度：$O(N)$

证明

下面证明 $ceil(n/(x+1)) = (n + x) / (x + 1)$ 。
**

当 $n = k * (x + 1)$ 的时候，即 $n$ 是 $x + 1$ 的整数倍时。

左边 $ceil(n / (x + 1)) = ceil(k (x + 1) / (x + 1)) = ceil(k) = k$。
右边 $(n + x) / (x + 1) = (k (x + 1) + x) / (x + 1) = k + x / (x + 1) = k + 0 = k$
左边等于右边。

当 $n = k (x + 1) + a$ 的时候，即 $n$ 除以 $x + 1$ 得 k，余数为 a 时（$1 <= a < (x + 1)$）。
左边 $ceil(n / (x + 1)) = ceil((k (x + 1) + a) / (x + 1)) = ceil(k + a / (x + 1)) = k + 1$。
右边 $(n + x) / (x + 1) = (k (x + 1) + a + x) / (x + 1) = ((k + 1)(x + 1) + a - 1) / (x + 1) = k + 1 + (a - 1) / (x + 1) = k + 1$。注意这里的 $1<= a < (x + 1)$，所以 $(a - 1) / (x + 1)$ 最小为 $(1 - 1) / (x + 1) = 0$；最大为 $(x - 1) / (x + 1) = 0$。
左边等于右边。

刷题心得

今天的题目代码简单，但是思考起来挺费劲，有点像脑筋急转弯。

OK，以上就是 @负雪明烛写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！

算法每日一题题解

【每日一题】781. 森林中的兔子

解题思路

证明

刷题心得