Rabbits in Forest

Rabbits in Forest

问题

森林中每个兔子都有自己的颜色，如果某些兔子说出与自己有相同颜色的兔子数量（不包括自己），那么如何根据这些数量计算最少有多少只兔子

解决方案

• 分析问题，如果每一个数量代表了一种颜色，那么只要判断这种数量至少有多少种颜色就可以了
• 文章中给出的解法，是用数量作为数组下标，这里提供另一种基于有序数组的解法，空间复杂度会低一点

class Solution {
    public int numRabbits(int[] answers) {
        if(answers.length==0)return 0;
                
        java.util.Arrays.sort(answers);
        int pre=answers[0],cur = pre,sum=0;
        for(int i=1;i<=answers.length;i++){
            if(i==answers.length){
                sum+=pre+1;
            }else{
                if(answers[i]==pre){
                    if(--cur<0){
                        cur = answers[i];
                        sum+=pre+1;
                    }
                }else{
                    sum+=pre+1;
                    cur = answers[i];
                }
                
                pre = answers[i];
            }
        }
        return sum;
    }
}

• 注意作者提供的解法中有这么一段

ans += Math.floorMod(-count[k], k+1) + count[k];

这里可以看做 count[k]基于k+1的上界（不是术语，方便理解而已，比如2基于5的上界是5，12基于5的上界是15，Math.ceil求的是一个数基于1的上界等等）