<span>【题解】力扣 781. 森林中的兔子</span>

题目来源

781. 森林中的兔子

思路

方法一

统计分配

用Map统计说同一个数字的兔子有几只。如果说同一个数字，定义为 \(color\) ，的兔子的个数，定义为 \(t\) ，

• 如果 \(t \le color\)，那么该颜色兔子的数量 \(ans = color+1\)

• 如果 $t > color $ ，

  • 如果 t%(color+1) != 0 那么该颜色的兔子数量为 \(ans = t/(color+1) * (color+1) + (color+1)\)

    这里 t/(color+1) * (color+1) 的操作相当于相对于 color+1 向下取整。

  • 如果 t%(color+1) == 0 那么给颜色的兔子数量为 \(ans = t/(color+1) * (color+1)\)

class Solution {
    public int numRabbits(int[] answers) {
        int len = answers.length;
        Map<Integer,Integer> map = new HashMap();
        
        // 统计说相同颜色的兔子数量
        for(int i = 0;i<len;i++){
            map.put(answers[i], map.getOrDefault(answers[i], 0)+1);
        }
        
        int res = 0;
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            int key = entry.getKey();
            int value = entry.getValue();
            int shan = map.get(key) / (key + 1);
            int yu = map.get(key) % (key+1);
            if(shan == 0){
                res += key+1;
            }else {
                res += shan * (key+1);
                if(yu!=0){
                    res += (key+1);
                }
            }
        }
        return res;
    }
}

• 时间复杂度： \(O(n)\)

• 空间复杂度： \(O(n)\)

方法二

模拟解法

先排序，然后遍历

class Solution {
    public int numRabbits(int[] answers) {
        int len = answers.length;
        Arrays.sort(answers);
        int ans = 0;
        for(int i = 0;i<len;i++){
            int cnt = answers[i];
            ans += cnt+1;
            int k = cnt;
            // 跳过「数值cnt」后面的cnt个「数值cnt」
            while(k>0 && i+1 < len && answers[i] == answers[i+1]){
                i++;
                k--;
            }
        }
        return ans;
    }
}

• 时间复杂度：\(O(nlogn)\)
• 空间复杂度：\(O(1)\)

参考来源

1. 宫水三叶