脚撕LeetCode(781)Medium

题目地址：https://leetcode-cn.com/problems/rabbits-in-forest/

森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。返回森林中兔子的最少数量。 https://leetcode-cn.com/problems/rabbits-in-forest/

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

输入: answers = [] 输出: 0 说明: answers 的长度最大为1000。 answers[i] 是在 [0, 999] 范围内的整数。 https://leetcode-cn.com/problems/rabbits-in-forest/

一、爆破法

爆破法的思路是，将相同数量的回答+1记录起来（也就是同色的兔子一共有多少只），放在map里面，key为回答的数量，value为这个数量的回答兔子数（比如两只兔子说有1只兔子跟我一样，那么key=2，value=2）

因为是统计最少数量，所以我们默认答案一样的尽可能是一个颜色（除非超过，比如3个人说有一只兔子颜色跟我一样。那么我们默认两个一样，第三个跟第四个一样但是第四个没说话）

因此我们的做法是，遍历数组，写入map，统计返回值的时候value/key，为 同色数量相同的兔子共有多少种颜色，然后再用颜色数量*key，如果value%key不为零，则再加一组key即可。

时间复杂度：O(n)，空间复杂度，O(1)

执行结果：

54 / 54 个通过测试用例

状态：通过

执行用时: 5 ms

内存消耗: 37.9 MB

public static int numRabbits(int[] answers) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int answer : answers) {
        map.put(answer + 1, map.getOrDefault(answer + 1, 0) + 1);
    }
    int sum = 0;
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        sum += entry.getValue() / entry.getKey() * entry.getKey();
        if (entry.getValue() % entry.getKey() != 0) {
            sum += entry.getKey();
        }
    }
    return sum;
}

二、官方提供的爆破法

这个爆破法和我们实现的爆破法思路相似，事实上创建了多个数组空间去完成爆破，但执行复杂度降低了

时间复杂度：O(n)，空间复杂度，O(1)

执行结果：

54 / 54 个通过测试用例

状态：通过

执行用时: 2 ms

内存消耗: 38 MB

public int numRabbits(int[] answers) {
        int[] count = new int[1000];
        for (int x: answers) count[x]++;

        int ans = 0;
        for (int k = 0; k < 1000; ++k)
            ans += Math.floorMod(-count[k], k+1) + count[k];
        return ans;
    }

三、评论区大佬的计数法

通过1000个元素的数组（题目中说过最多出现1000只兔子说话，每只说的数量是[0,999]），所以创建1000大小的数组

每个数组下标表示兔子喊的个数

当喊的个数为0或者喊n的兔子个数 % (n+1) = 1时，兔子总数+(n+1)

为什么是% = 1 呢 因为只要是超出n+1，的第一只兔子，我们就归类为另一个颜色，所以第一只兔子的时候count++就行，避免重复叠加。

时间复杂度：O(n)，空间复杂度，O(n)

执行结果：

54 / 54 个通过测试用例

状态：通过

执行用时: 0 ms

内存消耗: 37.7 MB

public int numRabbits(int[] answers) {
    int[] record = new int[1000];// 记录回答的数量
    int count = 0;
    for (int a : answers) {
        record[a]++;// 记录回答a的数量
        if (a == 0 || record[a] % (a + 1) == 1)// 回答a表示record[a]可容纳a+1只同颜色的兔子，超过要用另一种颜色
            count += a + 1;
    }
    return count;
}

讲解：

爆破法的思路很简单，直接将数据放在map里面，key为同色数量，value为此数量的个数。相比于评论区大佬提供的办法，map涉及到寻址，虽然map的算法很好，但是寻址还是需要经过一些计算，而直接使用数组最大的好处就是，直接使用数组寻址是直接用下标计算出数组头的偏移量，速度快很多，而且空间上的差距并没有想象的大，甚至map的空间消耗会更大一些。

总结：

有时候思考的太复杂反而效率和空间都跟不上，最简单的数组反而是算法中出现频率最高的，可能是工作用的集合多的原因，生疏了数组的强大作用和特性，在降低执行时间上，数组可是非常棒的一个工具。

以上就是leetcode.781.森林中的兔子(Medium)的全部内容