2000元阿里云代金券免费领取，2核4G云服务器仅664元/3年，新老用户都有优惠，立即抢购>>>
阿里云采购季（云主机223元/3年）活动入口：请点击进入>>>，
阿里云学生服务器（9.5元/月）购买入口：请点击进入>>>，
描述
在一个森林中，每个兔子都有一种颜色。兔子中的一部分（也可能是全部）会告诉你有多少兔子和它们有同样的颜色。这些答案被放在了一个数组中。
返回森林中兔子可能的最少的数量。
- 给定数组的长度不超过 1000.
- 数组内的每个元素的范围都在 [0, 999]中.
在线评测地址：领扣题库官网
样例1
输入: [1, 1, 2]
输出: 5
解释:
两个回答 "1" 的兔子可能是相同的颜色，姑且说它们为红色.
回答 "2" 的兔子一定不会是红色，不然与前面的答案冲突.
姑且认为回答 "2" 的兔子是蓝色.
那么一定还有 2 只蓝色的兔子在森林里不过没有回答问题.
所以森林里兔子的最少总数是 5, 3只回答问题的加上 2 只没回答的.样例2
输入: [10, 10, 10]
输出: 11解题思路
假如说一只兔子说有 x 只兔子颜色与自己相同, 那么可以说有 x + 1 只兔子是这种颜色.
假如说共有 a 只兔子说有 b 只兔子与自己颜色相同, 那么暂且可以认为它们是同一种颜色:
- 如果 a == b + 1 那么我们可以认为说话了的这a只兔子就是所有这种颜色的兔子
- 如果 a < b + 1 那么说明还有 b + 1 - a 只这种颜色的兔子并没有说话
- 如果 a > b + 1 那么说明不只一种颜色, 可以认为每 b + 1 只是一种颜色
所以, 我们的处理方式便是:
- 把数组中的每个数字都 + 1
- 统计数组中每个数字的数量
- 假设数组中的 a 有 b 个, 那么这b个a对应的最少的兔子的数量就是 ceil(b / a) * a
可以这样做是因为: 为了让总数最小, 我们总是尽可能认为两只兔子是同一颜色, 而说出了不同的数字的兔子必然不是同一颜色的.
class Solution {
public int numRabbits(int[] answers) {
int res = 0;
Map<Integer,Integer> map = new HashMap<>();
for(int answer : answers) {
map.put(answer,map.getOrDefault(answer,0)+1);
}
for(Integer n : map.keySet()) {
int group = map.get(n)/(n+1);
res += map.get(n)%(n+1) != 0 ? (group+1)*(n+1) : group*(n+1);
}
return res;
}
}更多题解参考：九章官网solution
