[leetcode/lintcode 题解] 阿里算法面试真题：森林中的兔子

描述
在一个森林中，每个兔子都有一种颜色。兔子中的一部分（也可能是全部）会告诉你有多少兔子和它们有同样的颜色。这些答案被放在了一个数组中。
返回森林中兔子可能的最少的数量。

1. 给定数组的长度不超过 1000.
2. 数组内的每个元素的范围都在 [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. 把数组中的每个数字都 + 1
2. 统计数组中每个数字的数量
3. 假设数组中的 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