781.森林中的兔子

问题描述

781. 森林中的兔子 (Medium)

森林中有未知数量的兔子。提问其中若干只兔子 "还有多少只兔子与你（指被提问的兔子）颜色相同?" ，将答案收集到一个整数数组 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

解题思路

从题目中给出的例子我们可以发现，要想让兔子数量最小，那么要尽量让回答结果相同的兔子是同一个颜色的；

我们用一个哈希表unordered_map<int, int> ump来记录每种结果有多少只兔子回答了，key为回答结果，value是回答该结果的兔子的数量；

如果ump[i] > i + 1，说明这批兔子至少有不止一种颜色，颜色数为(ump[i] - 1) / (i + 1) + 1，每种颜色有i + 1个兔子。

代码

class Solution {
  public:
    int numRabbits(vector<int> &answers) {
        unordered_map<int, int> ump;
        int res = 0;
        for (auto &num : answers) {
            ump[num]++;
        }
        for (auto &num : ump) {
            // if (num.second % (num.first + 1) == 0) {
            //     res += num.second;
            // } else {
            //     res  += (num.second / (num.first + 1) + 1) * (num.first + 1);
            // }
            res += ((num.second - 1) / (num.first + 1) + 1) * (num.first + 1);
        }
        return res;
    }
};