---

前言

這是刷算法題的第十六天，用到的語言是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）