0781. Rabbits in Forest¶
题目信息¶
- 题号:
0781
- 难度:
Medium
- 主题:
数组、分组计数、最小数量
- 原题:
- 重点:
每个回答
x表示森林中另有x只与自己同色的兔子,因此该颜色组大小为x + 1;不同颜色的兔子可以给出相同回答,需求森林兔子总数的最小值
题目重述¶
森林中每只接受询问的兔子都会回答:还有多少只兔子与自己颜色相同。数组 answers 记录这些回答,其中 answers[i] = x 表示第 i 只受访兔子声称,除自己之外还有 x 只同色兔子。
并非森林中的所有兔子都一定接受了询问。给出全部回答后,请返回与这些回答一致时,森林中兔子总数的最小可能值。给出相同回答的兔子不一定属于同一种颜色;若某个颜色组未全部出现在 answers 中,仍需把该组中未受访的兔子计入总数。
1 <= answers.length <= 1000,0 <= answers[i] < 1000。
自建示例¶
相同回答需要拆成多个颜色组:
输入:answers = [0,0,2,2,2,2]
输出:8
解释:两个回答 0 的兔子必须各自形成大小为 1 的颜色组。回答 2 表示颜色组大小为 3,四只这样的受访兔子至少需要分属两个颜色组,共计 6 只。因此最少有 1 + 1 + 6 = 8 只兔子。
只有一只兔子且回答零:
输入:answers = [0]
输出:1
解释:回答 0 表示没有其他兔子与它同色,所以该颜色组大小恰好为 1。输入也只有这一只受访兔子,最小森林规模就是 1。