0781. Rabbits in Forest

题目信息

题号:

0781

难度:

Medium

主题:

数组、分组计数、最小数量

原题:

LeetCode 0781

重点:

每个回答 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。