LeetCode 781. 森林中的兔子

Categories:

题目描述
思路分析
1. 解法一：计数分组（推荐）
相似题目

题目描述

✅ 781. 森林中的兔子

思路分析

解法一：计数分组（推荐）

核心思路：

每个回答 x 表示该兔子属于一个大小为 x + 1 的颜色组。

同一回答值可划分为多个组，组数为 ceil(cnt / (x + 1))。

结果为所有组大小之和。

复杂度分析：

时间复杂度：O(n)，其中 n 表示回答数量。

空间复杂度：O(n)，哈希表统计回答频次。

class Solution {
    public int numRabbits(int[] answers) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int a : answers) {
            cnt.put(a, cnt.getOrDefault(a, 0) + 1);
        }

        int res = 0;
        for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
            int x = e.getKey();
            int c = e.getValue();
            int group = x + 1;

            int groups = (c + group - 1) / group;
            res += groups * group;
        }

        return res;
    }
}

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

	res := 0
	for x, c := range cnt {
		group := x + 1
		groups := (c + group - 1) / group
		res += groups * group
	}

	return res
}

相似题目

题目	难度	考察点
781. 森林中的兔子	中等	分组计数
846. 一手顺子	中等	计数
1007. 行相等的最少多米诺旋转	中等	计数
1090. 受标签影响的最大值	中等	贪心
945. 使数组唯一的最小增量	中等	排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/25329346