Medium

题目描述

森林里有未知数量的兔子。我们询问了 n 只兔子"有多少只其他兔子和你颜色相同？"，并将答案收集在整数数组 answers 中，其中 answers[i] 是第 i 只兔子的答案。

给定数组 answers，返回森林中兔子的最少数量。

示例 1：

输入：answers = [1,1,2]
输出：5
解释：
回答 "1" 的两只兔子可能有相同的颜色，比如红色。
回答 "2" 的兔子不能是红色，否则他们的答案就不一致了。
设回答 "2" 的兔子为蓝色。
那么森林中应该有另外 2 只蓝色兔子没有回答问题。
因此森林中兔子的最少数量是 5：3 只回答问题的 + 2 只没有回答问题的。

示例 2：

输入：answers = [10,10,10]
输出：11

提示：

  • 1 <= answers.length <= 1000
  • 0 <= answers[i] < 1000

解题思路

解题思路

这道题的关键在于理解题目的逻辑：如果一只兔子回答"x"，说明包括它自己在内，同颜色的兔子总数是 x+1 只。

贪心策略分析：

为了使兔子总数最少，我们应该尽可能让相同答案的兔子属于同一颜色。具体来说：

  • 如果有 count 只兔子都回答"x"，那么每 (x+1) 只可以组成一个颜色组
  • 需要的颜色组数量为 ⌈count/(x+1)⌉，即 (count + x) / (x + 1)
  • 每个颜色组包含 (x+1) 只兔子

算法步骤：

  1. 统计每个答案出现的次数
  2. 对于答案为 x 且出现 count 次的情况：
    • 需要 ⌈count/(x+1)⌉ 个颜色组
    • 每组有 (x+1) 只兔子
    • 总贡献：⌈count/(x+1)⌉ × (x+1)
  3. 将所有答案的贡献相加

这种贪心策略是最优的，因为我们最大化了同色兔子的复用。

代码实现

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        unordered_map<int, int> count;
        for (int answer : answers) {
            count[answer]++;
        }
        
        int result = 0;
        for (auto& [answer, cnt] : count) {
            int groupSize = answer + 1;
            int groups = (cnt + groupSize - 1) / groupSize;
            result += groups * groupSize;
        }
        
        return result;
    }
};

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        from collections import Counter
        
        count = Counter(answers)
        result = 0
        
        for answer, cnt in count.items():
            group_size = answer + 1
            groups = (cnt + group_size - 1) // group_size
            result += groups * group_size
            
        return result

public class Solution {
    public int NumRabbits(int[] answers) {
        var count = new Dictionary<int, int>();
        foreach (int answer in answers) {
            count[answer] = count.GetValueOrDefault(answer, 0) + 1;
        }
        
        int result = 0;
        foreach (var kvp in count) {
            int answer = kvp.Key;
            int cnt = kvp.Value;
            int groupSize = answer + 1;
            int groups = (cnt + groupSize - 1) / groupSize;
            result += groups * groupSize;
        }
        
        return result;
    }
}

var numRabbits = function(answers) {
    const count = new Map();
    for (const answer of answers) {
        count.set(answer, (count.get(answer) || 0) + 1);
    }
    
    let result = 0;
    for (const [answer, cnt] of count) {
        const groupSize = answer + 1;
        const groups = Math.ceil(cnt / groupSize);
        result += groups * groupSize;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(k)

其中 n 是 answers 数组的长度，k 是不同答案的数量（最多为 1001）。

相关题目