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;

    }

};

巴特西

781. 森林中的兔子 (Medium)

问题描述

解题思路

代码

最新文章

热门文章