781. 森林中的兔子¶

难度：中等

题目¶

森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。

返回森林中兔子的最少数量。

示例:

输入: answers = [1, 1, 2]
输出: 5
解释:
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。

输入: answers = [10, 10, 10]
输出: 11

输入: answers = []
输出: 0

说明:

answers 的长度最大为1000。
answers[i] 是在 [0, 999] 范围内的整数。

Reference

题解¶

兔子的分类满足如下情况，设第\(i\)只兔子的报数为\(a_i\)，则：

若\(a_i \not = a_j\)，则第\(i\)只兔子与第\(j\)只兔子必然不属于一类
若\(a_i = a_j\)，则第\(i\)只兔子与第\(j\)只兔子可能属于一类，
第\(i\)只兔子所属的类中最多有\(a_i + 1\)只兔子

因此可以得出算法：统计相同数字\(a_i\)出现的次数\(b_j\)，对于每个数字，与之对应的最少的兔子数量为\(b'_j\)，则\(b'_j\)满足如下条件：

\(b'_j = k \times (a_i + 1), k\in \N\)
\(b'_j \geq b_j\)
\(b'_j - (a_i + 1) < b_j\)

即\(b'_j = \left\lceil\frac{b_j}{a_i + 1}\right\rceil\times (a_i + 1)\)

int numRabbits(int* answers, int answersSize){
    int hash[1000] = {0}, i = 0, ret = 0;
    for (i = 0; i < answersSize; i++)
        hash[answers[i]]++;
    for (i = 0; i < 1000; i++)
        ret += (hash[i] + i) / (i + 1) * (i + 1);
    return ret;
}

Python可以使用内置库collections中的Counter类统计数字的出现次数：

import collections

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        return sum(map(
            lambda args: sum(args) // (args[0] + 1) * (args[0] + 1)
            collections.Counter(answers).items()
        ))

781. 森林中的兔子¶

题目¶

题解¶

评论