力扣每日打卡16 781. 森林中的兔子(中等)

---

前言

这是刷算法题的第十六天，用到的语言是JS
题目：力扣 781. 森林中的兔子 (中等)

---

一、题目内容

森林中有未知数量的兔子。提问其中若干只兔子 “还有多少只兔子与你（指被提问的兔子）颜色相同?” ，将答案收集到一个整数数组 $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$

二、解题方法

1. 哈希函数（来自评论区大佬的解题方法）

挺好想的吧，第i个兔子回答有x个相同的亲兄弟，加上它自己，这种兔子至少有x + 1个，当第j个兔子也回答有x个亲兄弟时，其实就两种情况：

1. 第j个兔子和第i个兔子同属一个阵营，它们互为亲兄弟
2. 第j个兔子和第i个兔子不属于同一个阵营，它们不是亲兄弟

下面具体分析：
当有兔子回答x时，一定存在一个最多容纳x+1个兔子的兔子阵营，且同属于一个阵营的兔子的回答都是一样的，都是x，因此我们记录有多少只兔子回答了x，即mp[x] = y就表示有y只兔子回答了 x
解释为：一个最多容纳x+1只兔子的兔子阵营，找到了y只兔子在这个阵营中，y == 1表示这个阵营第一次出现，而当y == x + 1时表示这个阵营已经满了，后续还有兔子回答x时已经是另一个新阵营的兔子了，咱们只在y == 1时收集答案，即只出现新阵营时才收集答案，这样就避免了重复计算了和漏计算

代码如下（示例）：

/*** @param {number[]} answers* @return {number}*/
var numRabbits = function (answers) {// 哈希表？let count = 0const map = new Map()for (const x of answers) {// 记录当前答案出现的次数, 一开始是0，首次添加时为1map.set(x, (map.get(x) || 0) + 1)if (map.get(x) > x + 1) map.set(x, 1) // 产生了新的颜色阵营if (map.get(x) === 1) count += x + 1 // 出现新阵营 或者 答案次数只有1的话，就加上阵营的兔子数量// 补充，为什么两个if调换顺序就出问题// 调换后，错误的新增计数： // 假设某个颜色（兔子回答） x 的出现次数当前为 x + 1，而这时有另一个兔子也说 x。因为我们先检查了 map.get(x) === 1，会在这个时候错误地将这个阵营的数量加到 count 中，即使它实际上应该被标记为已满。// 没有正确重置计数：// 如果没有首先检查是否超过最大次数（x + 1），那么我们就无法及时重置计数为 1，而是错误地累加到现有计数基础上，这会导致最终的计数不准确，增加了不该计数的兔子。}return count
}

---

2.官方题解

2.1 方法一：贪心

代码如下（示例）：

var numRabbits = function(answers) {const count = new Map();for (const y of answers) {count.set(y, (count.get(y) || 0) + 1);}let ans = 0;for (const [y, x] of count.entries()) {ans += Math.floor((x + y) / (y + 1)) * (y + 1);}return ans;
};作者：力扣官方题解
链接：https://leetcode.cn/problems/rabbits-in-forest/solutions/698444/sen-lin-zhong-de-tu-zi-by-leetcode-solut-kvla/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析：

时间复杂度： $O(n)$，其中 $n$ 是数组 $answers$ 的长度。

空间复杂度： $O(n)$。最坏情况下，哈希表中含有 $n$ 个元素。

链接：力扣本题官方题解
来源：力扣（LeetCode）