【4.4】LeetCode每日一题· 森林中的兔子

2021年04月04日 12时26分

标签： LeetCode 数学贪心

## 题目描述
森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在`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] 范围内的整数。
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/rabbits-in-forest "题目链接")
> 华为3.31笔试第3题

## 解题思路
考虑贪心，如果有很多兔子说**和自己相同颜色的兔子的数量相同**，那么我们可以将这些兔子分成若干组，假设每一组兔子的颜色都相同。

具体地，设有$$a$$只兔子说，有$$b$$只兔子的颜色和它的颜色都一样（说白了就是数组中有$$a$$个元素值为$$b$$),

那么，可以讨论$$a$$和$$b$$之间的数量关系

$$a \\leq b+1$$
	此时，可以认为有$$b+1$$只颜色相同的兔子，并且其他兔子的颜色都和这些兔子不同。
	> $$a = b+1$$	时，对于每只兔子来说，有另外的$$b$$只兔子和它颜色相同，加上他自己，所以有$$b+1$$只颜色相同的兔子；
	
	> $$a < b+1 $$时，有$$(b + 1 - a)$$只兔子没有回答；
	
	> 假设还有其他兔子颜色和这些兔子相同，设颜色为R，设这只兔子说有$$c (c \\neq b)$$只其他兔子颜色也为R，则有$$c+1$$只颜色为R的兔子；
	> 而根据前提$$a$$只兔子说其他有$$b$$只兔子颜色为R，那么有$$b+1$$只兔子颜色为R，因此$$c+1 = b+1$$，和$$c \neq b$$矛盾，因此其他兔子的颜色都和这些兔子不同。
2. 
 
 $$a \> b+1$$
	此时不能认为只有$$b+1$$只颜色相同的兔子（因为回答的兔子数量都大于$$b+1$$了），而是有不同颜色的兔子数量相同。可以将其分为$$\lceil \frac{a}{b+1} \rceil$$个组，每一组中有$$b+1$$只颜色相同的兔子，因此总共有$$\lceil \frac{a}{b+1} \rceil \times (b+1)$$只兔子。

其实分析一下，12情况可以合并，使用
```math
\displaystyle
\lceil \frac{a}{b+1} \rceil \times (b+1)
```
计算** 有$$a$$只兔子说，有$$b$$只兔子的颜色和它的颜色都一样**时，这些兔子的个数。

因此，我们只需要统计数组中个元素的个数，然后使用如上公式求出每组兔子的个数，最后求和即可。

Tips：
```math
\displaystyle
\lceil \frac{a}{b} \rceil = \lfloor \frac{a+b-1}{b} \rfloor 
```
### 代码
```cpp
class Solution {
public:
    int numRabbits(vector<int>& answers) {
        unordered_map<int, int> mp;
        int res = 0;
        for(int& answer: answers){
            mp[answer]++;
        }
        for(auto& item: mp){
            res += (item.second+item.first) / (item.first+1) * (item.first+1);
        }
        return res;
    }
};
```

## 用时和内存
> 执行用时：4 ms，在所有 C++提交中击败了88.05%的用户
> 内存消耗：8.4 MB，在所有 C++提交中击败了55.38%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.4】LeetCode每日一题· 森林中的兔子

所有评论

暂无评论

新增评论