LeetCode 781. 森林中的兔子

约 4 分钟
文章信息 9 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 腾讯 字节 阿里 亚马逊
标签
数组 哈希表 数学 贪心

题目描述

✅ 781. 森林中的兔子

image-20260929002002966

题意分析

每个回答 x 表示这只兔子之外，还有 x 只与它颜色相同的兔子，所以这一颜色在森林中共有 x + 1 只。只有部分兔子接受询问，未出现在回答数组中的兔子也可能必须存在。

求与全部回答一致的最小森林总数。相同回答可以来自同一种颜色，也可以来自不同颜色；不同回答则不可能属于同一种颜色，因为同色兔子的总数应相同。

解法：按回答值分组计数

核心思路

[!blue]

先按回答值统计频次。对于回答 x 的 count 只兔子，每一种可能的颜色都必须恰好有 groupSize = x + 1 只，因此一组最多容纳 groupSize 只已经回答的兔子。

要容纳全部 count 个回答，颜色组数至少为 ceil(count / groupSize)。即使最后不足一组，也需要承认这一整组兔子的存在，缺少的只是没有接受询问的同色兔子，不能只按已回答数量计数。

这个下界可以达到：把相同回答尽量装满每组，剩余不足一组的放到新颜色里，再补足未回答兔子；为各组选择互不相同的颜色，就与所有回答一致。因此该回答值的最少贡献是组数乘组大小。

不同回答值不能共享颜色，所以各自的最小贡献可以独立求出后相加。整数向上取整用 (count + groupSize - 1) / groupSize，无需浮点；回答零时组大小为一，每只都必须属于不同颜色，也由同一公式处理。

解题步骤

  1. 用哈希表统计每个回答值的出现次数。
  2. 对回答 x，令组大小为 x + 1，读取该回答的次数 count。
  3. 计算最少组数 (count + groupSize - 1) / groupSize，将组数乘组大小加入总数。
  4. 遍历所有回答值后返回总数。

代码实现

class Solution {
    public int numRabbits(int[] answers) {
        Map<Integer, Integer> frequency = new HashMap<>();

        for (int answer : answers) {
            frequency.put(answer, frequency.getOrDefault(answer, 0) + 1);
        }

        int ans = 0;

        for (Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
            // 回答不同不能同组，回答相同的组大小是回答加一
            int groupSize = entry.getKey() + 1;
            int count = entry.getValue();
            // 不足一组仍需补齐，使用整数向上取整
            int groups = (count + groupSize - 1) / groupSize;

            ans += groups * groupSize;
        }

        return ans;
    }
}

func numRabbits(answers []int) int {
    frequency := make(map[int]int)
    for _, answer := range answers {
        frequency[answer]++
    }

    ans := 0
    for answer, count := range frequency {
        // 回答不同不能同组，回答相同的组大小是回答加一
        groupSize := answer + 1
        // 不足一组仍需补齐，使用整数向上取整
        groups := (count + groupSize - 1) / groupSize
        ans += groups * groupSize
    }
    return ans
}

复杂度分析

  • 时间复杂度：期望 $O(n)$，统计及遍历频次表。
  • 空间复杂度：$O(u)$，u 是不同回答数量。

关键点总结

[!green]

  • 回答的是其他同色兔子数，组大小需要加上回答者自己。
  • 相同回答可以分属多种颜色，每组容量由回答确定，不能无限合并。
  • 不满的一组也要补齐真实兔子数，未回答不代表不存在。
  • 分组数量有容量下界，填满分组的构造能达到下界，因此得到的是最少总数。

易错点总结

[!yellow]

  • 把组大小写成回答值，会漏掉回答者自己，回答零时还会导致除零。
  • 直接用整数整除而不向上取整，会丢掉最后一组的需求。
  • 将相同回答全部视为同一种颜色，可能让同色兔子数超过回答允许的组大小。
  • 每遇到一个回答就单独增加一整组，又会忽略这些回答可能共享颜色，得到过大的答案。
  • 只累计参与回答的兔子数，会遗漏为满足回答必须补齐的未受访兔子。

相似题目

题目 难度 关联与区别
2244. 完成所有任务需要的最少轮数 中等 同样把同类元素分成若干组并最小化组数，本题回答x限定每组容量x+1，不足一组也要补足真实兔子数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/25329346
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！