LeetCode刷题【781】森林中的兔子

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

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

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

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

输入: answers = []
输出: 0

说明:

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

题解

题中给出了 answers[i]的范围在0-999，所以我在声明numCount数组的时候多加了一位，用来保存最终结果，也可以单独声明一个变量。顺便存在一个数组里的作法只是图省个事而已。

那么来分析一下，要求最小可能的数量，可以假定，当前n+1次遇到说和自己颜色一样的兔子还有n个的时候，都是同一个颜色的兔子。

如果在遇到了n+1个兔子之后还遇到了说和自己颜色一样的兔子还有n个的时候，我们可以认为这只兔子的颜色和前面说n只的颜色是不一样的。那么就应该有另外n+1只后面这个颜色的兔子。

定义一个numCount数组，key就是说还有n，当第一次遇到的时候，就给加上n+1只的结果，同时value值统计遇到了几只说n的兔子，如果统计有n+1只说了n的兔子之后，就置零，后面再遇到就是其他的颜色了

public class LeetCode781 {
    public int numRabbits(int[] answers) {
        int[] numCount = new int[1001];
        for (int num : answers) {
            if(numCount[num] == 0){
                //没有遇到过，加上下数量
                //如果大于0，则说明已经遇到过不再重复计数
                numCount[1000] += num+1;
            }
            //对应数量的+1
            numCount[num]++;
            if (numCount[num] == num+1){
                //已经有N+1只兔子说了有N只和自己颜色一样
                //这时候可以认为，这种颜色的最小可能数量已经达到了
                //可以清空，后面再有说这个数量的可以认为是其他的颜色
                numCount[num] = 0;
            }
        }
        return numCount[1000];
    }
}