LC 781. 森林中的兔子
题目描述
这是 LeetCode 上的 781. 森林中的兔子 ,难度为 中等。
森林中,每个兔子都有颜色。其中一些兔子(可能是全部)告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers
数组里。
返回森林中兔子的最少数量。
示例:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16输入: answers = [1, 1, 2]
输出: 5
解释:
两只回答了 "1" 的兔子可能有相同的颜色,设为红色。
之后回答了 "2" 的兔子不会是红色,否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。
此外,森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。
输入: answers = [10, 10, 10]
输出: 11
输入: answers = []
输出: 0
说明:
answers
的长度最大为 $1000$answers[i]
是在 $[0, 999]$ 范围内的整数。
基本分析
首先,兔子它不会说谎 (`・ω・´),因此我们可以得出以下结论:
- 同一颜色的兔子回答的数值必然是一样的
- 但回答同样数值的,不一定就是同颜色兔子
举个🌰,假如有 3 只白兔,每只白兔的回答必然都是 2(对应结论 1);但假如有兔子回答了数值 2,可能只是三只白兔,也可能是三只白兔和三只灰兔同时进行了回答(对应结论 2)。
答案要我们求最少的兔子数量。
不妨设有某种颜色的兔子 $m$ 只,它们回答的答案数值为 $cnt$,那么 $m$ 和 $cnt$ 满足什么关系?
显然两者关系为 $m = cnt + 1$。
但如果是在 $answers$ 数组里,回答 $cnt$ 的数量为 $t$ 的话呢?这时候我们需要分情况讨论:
- $t \leqslant cnt + 1$ : 为达到「最少的兔子数量」,我们可以假定这 $t$ 只兔子为同一颜色,这样能够满足题意,同时不会导致「额外」兔子数量增加(颜色数量最少)。
- $t > cnt + 1$ : 我们知道回答 $cnt$ 的兔子应该有 $cnt + 1$ 只。这时候说明有数量相同的不同颜色的兔子进行了回答。为达到「最少的兔子数量」,我们应当将 $t$ 分为若干种颜色,并尽可能让某一种颜色的兔子为 $cnt + 1$ 只,这样能够满足题意,同时不会导致「额外」兔子数量增加(颜色数量最少)。
换句话说,我们应该让「同一颜色的兔子数量」尽量多,从而实现「总的兔子数量」最少。
证明
我们来证明一下,为什么这样的贪心思路是对的:
基于上述分析,我们其实是在处理 $answers$ 数组中每一个 $cnt$ ,使得满足题意的前提下,数值 $cnt$ 带来的影响(总的兔子数量,或者说总的颜色数量)最小。
首先 $answers$ 中的每个数都会导致我们总的兔子数量增加,因此我们应该「让 $answers$ 的数字尽可能变少」,也就是我们需要去抵消掉 $answers$ 中的一些数字。
对于 $answers$ 中的某个 $cnt$ 而言(注意是某个 $cnt$,含义为一只兔子的回答),必然代表了有 $cnt + 1$ 只兔子,同时也代表了数值 $cnt$ 最多在 $answers$ 数组中出现 $cnt + 1$ 次(与其颜色相同的兔子都进行了回答)。
这时候我们可以从数组中移走 $cnt + 1$ 个数值 $cnt$(如果有的话)。
当每次处理 $cnt$ 的时候,我们都执行这样的抵消操作。最后得到的 $answers$ 数值数量必然最少(而固定),抵消完成后的 $answers$ 中的每个 $cnt$ 对答案的影响也固定(增加 $cnt + 1$),从而实现「总的兔子数量」最少。
相反,如果不执行这样的操作的话,得到的 $answers$ 数值数量必然会更多,「总的兔子数量」也必然会更多,也必然不会比这样做法更优。
模拟解法
按照上述思路,我们可以先对 $answers$ 进行排序,然后根据遍历到某个 $cnt$ 时,将其对答案的影响应用到 $ans$ 中(ans += cnt + 1
),并将后面的 $cnt$ 个 $cnt$ 进行忽略。
代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public int numRabbits(int[] cs) {
Arrays.sort(cs);
int n = cs.length;
int ans = 0;
for (int i = 0; i < n; i++) {
int cnt = cs[i];
ans += cnt + 1;
// 跳过「数值 cnt」后面的 cnt 个「数值 cnt」
int k = cnt;
while (k-- > 0 && i + 1 < n && cs[i] == cs[i + 1]) i++;
}
return ans;
}
}
- 时间复杂度:$O(n\log{n})$
- 空间复杂度:$O(1)$
统计分配
我们也可以先对所有出现过的数字进行统计,然后再对数值进行(颜色)分配。
代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
int N = 1009;
int[] counts = new int[N];
public int numRabbits(int[] cs) {
// counts[x] = cnt 代表在 cs 中数值 x 的数量为 cnt
for (int i : cs) counts[i]++;
int ans = counts[0];
for (int i = 1; i < N; i++) {
int per = i + 1;
int cnt = counts[i];
int k = cnt / per;
if (k * per < cnt) k++;
ans += k * per;
}
return ans;
}
}
- 时间复杂度:$O(n)$
- 空间复杂度:$O(n)$
拓展
保持题目现有的条件不变,假定颜色相同的兔子至少有一只发声,问题改为「问兔子颜色数量可能有多少种」,又该如何求解呢?
最后
这是我们「刷穿 LeetCode」系列文章的第 No.781
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!