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)。