力扣算法：森林中的兔子

• 一、森林中的兔子
• • 1、问题
  • 2、思路
  • 3、代码
  • 4、时间与空间复杂度
• 备注

一、森林中的兔子

1、问题

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

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

示例1:

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

示例2:

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

示例3:

输入: answers = []
输出: 0

说明:

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

2、思路

如果有 x 只兔子都回答 y，则至少有 ⌈x/(y+1)⌉种不同的颜色，且每种颜色有 y+1 只兔子，因此兔子数至少为⌈x/(y+1)⌉*(y+1)

例如：

如果5出现了8次， 那么至少得 2*（5+1）只兔子；
如果5出现了6次呢？ 至少需要6只兔子；
如果5出现了3次呢？ 还是6只兔子；

• 我们用哈希表进行统计，当 key 出现了 value 次：
• 如果 value %（key+1） == 0， 需要（value /（key+1））*（key+1）只兔子；
• 如果没有整除， 则至少需要( value /（key+1）+1）* （key+1）只兔子；

向上取整 (value+key) //（key+1）*（key+1）

3、代码

#coding:utf-8
from typing import List
import collections
class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        return sum((k+v)//(k+1)*(k+1) for k,v in collections.Counter(answers).items())


if __name__ == "__main__":
    # answers = [1, 1, 2]
    # answers = [10, 10, 10]
    # answers = []
    # answers = [1,0,1,0,0]
    answers = [0, 0, 1, 1, 1]

    print(Solution().numRabbits(answers))

4、时间与空间复杂度

时间复杂度：O(n)
n为answers 数组长度

空间复杂度：O(n)
n为哈希表的大小

备注

1、参考：
LeetCode-Solution
https://leetcode-cn.com/problems/rabbits-in-forest/solution/sen-lin-zhong-de-tu-zi-by-leetcode-solut-kvla/

2、Python3 字典 items() 方法：

• Python 字典 items() 方法以列表返回视图对象，是一个可遍历的key/value 对。
• dict.keys()、dict.values() 和 dict.items() 返回的都是视图对象（ view objects），提供了字典实体的动态视图，这就意味着字典改变，视图也会跟着变化。
• 视图对象不是列表，不支持索引，可以使用 list() 来转换为列表。
• 我们不能对视图对象进行任何的修改，因为字典的视图对象都是只读的。

#遍历例子
dict = {'Name': 'Runoob', 'Age': 7}
for i,j in dict.items():
    print(i, ":\t", j)
    
#输出：
#Name :   Runoob
#Age :    7



#将字典的 key 和 value 组成一个新的列表：
d={1:"a",2:"b",3:"c"}
result=[]
for k,v in d.items():
    result.append(k)
    result.append(v)
print(result)

#输出：
#[1, 'a', 2, 'b', 3, 'c']