0781. 森林中的兔子【中等】
1. 📝 题目描述
森林中有未知数量的兔子。提问其中若干只兔子 "还有多少只兔子与你（指被提问的兔子）颜色相同?"，将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。
给你数组 answers，返回森林中兔子的最少数量。
示例 1：
txt
输入：answers = [1,1,2]
输出：5
解释：
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5 只：3 只回答的和 2 只没有回答的。1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
示例 2：
txt
输入：answers = [10,10,10]
输出：111
2
2
提示：
1 <= answers.length <= 10000 <= answers[i] < 1000
2. 🎯 s.1 - 贪心 + 哈希表
c
int numRabbits(int* answers, int answersSize) {
int count[1000] = {0};
for (int i = 0; i < answersSize; i++) count[answers[i]]++;
int res = 0;
for (int i = 0; i < 1000; i++) {
if (count[i] > 0) {
int group = i + 1;
res += ((count[i] + group - 1) / group) * group;
}
}
return res;
}1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
js
/**
* @param {number[]} answers
* @return {number}
*/
var numRabbits = function (answers) {
const map = new Map()
let res = 0
for (const a of answers) {
if (map.has(a) && map.get(a) > 0) {
map.set(a, map.get(a) - 1)
} else {
res += a + 1
map.set(a, a)
}
}
return res
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
py
class Solution:
def numRabbits(self, answers: List[int]) -> int:
from collections import Counter
count = Counter(answers)
res = 0
for a, c in count.items():
group = a + 1
res += ((c + group - 1) // group) * group
return res1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
- 时间复杂度：
- 空间复杂度：
算法思路：
- 回答 a 的兔子最多 a+1 只一组，统计每个回答的出现次数
- 对回答 a 出现 c 次，至少需要 ⌈c/(a+1)⌉ 组，每组 a+1 只