LeetCode 781. 森林中的兔子

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

题目描述

✅ 781. 森林中的兔子

题意分析

每只兔子回答“还有多少只兔子和自己颜色相同”。如果回答为 x，说明这种颜色一组共有 x + 1 只兔子。

相同回答的兔子可以分到同一颜色组，但每组最多容纳 x + 1 只。若回答 x 的兔子有 count 只，就需要 ceil(count / (x + 1)) 组。

每组都贡献 x + 1 只兔子，即使其中有些兔子没有出现在回答列表中，也要算入森林总数。

解法：按回答值分组计数

核心思路

一只兔子回答 x，意味着它所在颜色组的总大小恰好是 g = x + 1。同色兔子的回答一定相同，因此回答值不同的兔子不能放进同一颜色组，各回答值可以独立处理。

设回答 x 出现 c 次。一个对应颜色组最多容纳 g 只已回答兔子，所以至少需要

\[\left\lceil \frac{c}{g}\right\rceil\]

个颜色组；每个组真实存在 g 只兔子，即使其中部分兔子没有参与回答也必须计入。该回答值对总数的最小贡献为

\[\left\lceil \frac{c}{g}\right\rceil \cdot g\]

这是一个可达到的下界：把回答相同的兔子每 g 只装满一组，最后不足 g 只的部分单独开一组，再用未回答兔子补足即可。因此对每个回答值分别取最小值后求和，就是全局最优解。

解题步骤

  • 用哈希表统计每个回答值 x 的出现次数 c。
  • 计算颜色组大小 g = x + 1。
  • 用整数公式 (c + g - 1) / g 计算向上取整后的组数。
  • 将 组数 * g 累加到答案。
  • 遍历完所有回答值后返回答案。

例如 [1,1,1,2]：回答 1 的三只兔子每组容量为 2，需要两组，贡献 4；回答 2 的一只兔子所在组容量为 3，贡献 3；总数最少为 7。

代码实现

import java.util.HashMap;
import java.util.Map;

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(1)$。
  • 空间复杂度：$O(u)$，其中 $u$ 是不同回答值的数量，最坏为 $O(n)$。

关键点总结

  • 回答 x 表示颜色组大小是 x + 1，不是 x。
  • 相同回答可以共享颜色组，但每组最多容纳 x + 1 只已回答兔子。
  • 最后一组即使未装满，也必须按完整组大小计入未回答兔子。
  • 正确性证明要同时说明“至少需要这些组”和“按容量分组确实能达到该下界”。

易错点总结

  • 每个回答值只开一组：当出现次数超过组容量时会少算。
  • 每只兔子各开一组：没有把相同回答的兔子尽量合并，会多算。
  • 使用整除而不向上取整：不足一组的剩余兔子会被漏掉。
  • 最后一组按已回答人数计数：未参与回答的同色兔子也属于森林总数。
  • 跳过回答 0：它表示该兔子颜色唯一，每只仍贡献 1。

相似题目

题目 难度 考察点
169. 多数元素 简单 同样先做频率统计，但只需要找出超过半数的那个键
347. 前 K 个高频元素 中等 频率表建好后要按次数排序或用堆取前 K，重点在选择而非计数
451. 根据字符出现频率排序 中等 频率表用于重排输出串，考察计数与排序的衔接
621. 任务调度器 中等 也是按频率分桶，但桶的容量由冷却时间决定且需要考虑最大频次
452. 用最少数量的箭引爆气球 中等 同为"最少分组"，但分组条件是区间重叠，需要排序后贪心扫描