森林中的兔子

题目

题目来源：力扣（LeetCode）

森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。

返回森林中兔子的最少数量。

示例:
输入: answers = [1, 1, 2]
输出: 5
解释:
两只回答了 “1” 的兔子可能有相同的颜色，设为红色。
之后回答了 “2” 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 “2” 的兔子为蓝色。
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。

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

输入: answers = []
输出: 0

思路分析

1. 如果一只兔子说还有n只兔子与它有相同颜色，那么必然存在n + 1只兔子。
2. answers中并不包含所有兔子，也就是说[2]、[2, 2]、[2, 2, 2]三种情况其实是一样的。
3. 如果answers = [2, 2, 2]，只有当兔子数量为3只时，才能满足任意一只能告诉你还有2只与它有相同颜 色。
4. 如果answers = [2, 2, 2, 2]，此时回答可以拆分成两组，分别是[2, 2, 2]和[2]，共有6只兔子。
5. 因此问题就转换为，将answers按照回答数量分类，并统计所有分类的兔子数量。
6. 如果每类回答ans的数量有count个，那么兔子一共可以分为Math.ceil(count / (ans + 1))组，每组ans + 1只。
7. 因此每类回答对应的兔子数量为Math.ceil(count / (ans + 1)) * (ans + 1)。

/**
 * @param {number[]} answers
 * @return {number}
 */
 var numRabbits = function (answers) {
  // 用map缓存每一种回答的数量
  let map = new Map();
  // 缓存结果 最少的兔子数量
  let result = 0;
  // 遍历所有回答，统计每一种回答出现的次数
  for (const ans of answers) {
    map.set(ans, map.has(ans) ? map.get(ans) + 1 : 1);
  }
  // 根据每一种回答的次数，计算兔子🐰的数量
  for (const [ans, count] of map) {
    // 统计每一类回答对应的兔子的数量
    result +=
      // 计算每一类回答可以分为几组
      Math.ceil(count / (ans + 1)) *
      // 每一组兔子🐰的数量
      (ans + 1)
  }
  return result;
};