LeetCode781 森林中的兔子
问题描述
在一片神秘的森林里，住着许多兔子，但是我们并不知道兔子的具体数量。现在，我们对其中若干只兔子进行提问，问题是 “还有多少只兔子与你（指被提问的兔子）颜色相同？” 我们将每只兔子的回答收集起来，存放在一个整数数组 answers 中，其中 answers[i] 表示第 i 只兔子的回答。我们的任务是根据这个数组，计算出森林中兔子的最少数量。
示例分析
假设 answers = [1, 1, 2]。
- 有两只兔子回答 “1”，这意味着它们认为还有 1 只兔子和自己颜色相同，所以这两只兔子很可能是同一种颜色，这种颜色的兔子总数为
1 + 1 = 2只。 - 有一只兔子回答 “2”，它表示还有 2 只兔子和自己颜色相同，那么这种颜色的兔子总数为
2 + 1 = 3只。 - 综合起来，森林中兔子的最少数量就是
2 + 3 = 5只。
解题思路
为了计算森林中兔子的最少数量，我们可以根据兔子的回答来分析。如果一只兔子回答有 k 只兔子和它颜色相同，那么包括这只兔子在内，同颜色的兔子一共有 k + 1 只。
我们可以使用哈希表（在 C 语言中可以用数组模拟）来统计每种回答出现的次数。对于每种回答 k，如果有 n 只兔子都回答 k，那么至少有 (n + k) / (k + 1) 种不同颜色的兔子群体，每种群体有 k + 1 只兔子。
代码实现
#include <stdio.h>
#include <stdlib.h>#define MAX_ANSWER 1000int numRabbits(int* answers, int answersSize) {int count[MAX_ANSWER + 1] = {0};// 统计每种回答出现的次数for (int i = 0; i < answersSize; i++) {count[answers[i]]++;}int total = 0;// 计算每种颜色的兔子数量for (int i = 0; i <= MAX_ANSWER; i++) {if (count[i] > 0) {// 计算这种颜色的兔子数量int x = i;int cnt = count[i];// 每 (x + 1) 只兔子为一组int groups = (cnt + x) / (x + 1);total += groups * (x + 1);}}return total;
}int main() {int answers[] = {1, 1, 2};int answersSize = sizeof(answers) / sizeof(answers[0]);int result = numRabbits(answers, answersSize);printf("Minimum number of rabbits: %d\n", result); return 0;
}代码详细解释
1. 头文件与宏定义
#include <stdio.h>
#include <stdlib.h>#define MAX_ANSWER 1000
#include <stdio.h>：引入标准输入输出库，用于后续的printf函数输出结果。#include <stdlib.h>：引入标准库，这里虽然代码中未直接使用库中的函数，但在更复杂的应用场景下可能会用到，提前引入作为储备。#define MAX_ANSWER 1000：定义一个宏MAX_ANSWER，表示兔子回答的最大可能值。这有助于后续代码中数组的创建和遍历范围的确定。
2. numRabbits 函数
int numRabbits(int* answers, int answersSize) {int count[MAX_ANSWER + 1] = {0};// 统计每种回答出现的次数for (int i = 0; i < answersSize; i++) {count[answers[i]]++;}int total = 0;// 计算每种颜色的兔子数量for (int i = 0; i <= MAX_ANSWER; i++) {if (count[i] > 0) {// 计算这种颜色的兔子数量int x = i;int cnt = count[i];// 每 (x + 1) 只兔子为一组int groups = (cnt + x) / (x + 1);total += groups * (x + 1);}}return total;
}
int count[MAX_ANSWER + 1] = {0};：创建一个长度为MAX_ANSWER + 1的数组count，用于统计每种回答出现的次数，初始值都设为 0。- 第一个
for循环：遍历answers数组，对于每个回答answers[i]，将count[answers[i]]的值加 1，从而统计出每种回答出现的次数。 int total = 0;：初始化一个变量total，用于存储最终计算出的兔子最少总数。- 第二个
for循环：遍历count数组，当count[i] > 0时，说明有兔子给出了回答i。int x = i;和int cnt = count[i];：将i赋值给x，将count[i]赋值给cnt，方便后续计算。int groups = (cnt + x) / (x + 1);：计算至少有多少组颜色相同的兔子群体。total += groups * (x + 1);：将每组兔子的数量乘以组数，累加到total中。
3. main 函数
int main() {int answers[] = {1, 1, 2};int answersSize = sizeof(answers) / sizeof(answers[0]);int result = numRabbits(answers, answersSize);printf("Minimum number of rabbits: %d\n", result); return 0;
}
- 定义一个示例数组
answers，并计算其长度answersSize。 - 调用
numRabbits函数计算兔子的最少数量，将结果存储在result中。 - 使用
printf函数输出结果。
复杂度分析
- 时间复杂度：代码中有两个主要的
for循环。第一个循环遍历answers数组，时间复杂度为 O(n)，其中 n 是answers数组的长度。第二个循环遍历count数组，由于count数组的长度是固定的（由MAX_ANSWER决定），可以看作一个常数，所以这个循环的时间复杂度为O(1)。综合起来，总的时间复杂度为 O(n)。 - 空间复杂度：使用了一个长度为
MAX_ANSWER + 1的数组count来统计回答次数，由于MAX_ANSWER是一个常数，所以空间复杂度为 O(1)。