森林中的兔子

发表于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，781. 森林中的兔子

先看题目描述

cuhwEd.png

算法和思路

哈希表

我们可以将 answers 中值相同的元素分为一组，构造一个哈希表，以颜色的总兔子数为 key，当前发现该颜色的兔子数为 value，以数组 [1，1，1，2] 为例，初始化 ans = 0，遍历到第一个元素 1 时，说明该颜色的兔子有两只，哈希表为空，说明之前没有统计过该颜色的兔子，因此将 ans 加 2，并将键值对 <2，1> 存入哈希表中，表示该颜色的兔子目前发现了一只；再遍历到第二个元素 1，发现哈希表中的键中存在 2，且其对应的值为 1 小于 2，因此我们发现了该颜色的第二只兔子，将键值对改为 <2，2>；遍历到第三个元素 1 时，发现哈希表中存在键值对 <2，2>，表示上一种颜色的两只兔子已经全部找到了，那么就说明该兔子是另一种颜色，且该颜色的兔子也是两只，将键值对改为 <2，1>，并将 ans 加 2；最后是遍历到元素 2，此时哈希表中不存在键 3，直接将 ans 加 3，并存入键值对 <3，1>

算法步骤：

  • 初始化 ans = 0，遍历数组 answers：
    • 对于当前元素 answer。令 num = answer + 1
      • 若哈希表中不存在键 num 或其对应的值与 num 相等，则将 ans 加上 num
      • 否则，令 num 对应的 value 加 1
  • 最后返回 ans 即可

算法源码

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int numRabbits(int[] answers) {
        Map<Integer, Integer> map = new HashMap<>();
        int ans = 0;
        for (int answer : answers) {
            int num = answer+ 1;
            if (!map.containsKey(num) || map.get(num) == num) {
                ans += num;
                map.put(num, 1);
            } else {
                map.put(num, map.get(num) + 1);
            }
        }
        return ans;
    }
}

下面是看运行效率比较快的代码看到的一个写法，思路是一致的，但是使用频次数组代替哈希表，运行效率更高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int numRabbits(int[] answers) {
        int[] cnt = new int[1001];
        int ans = 0;
        for (int answer : answers) {
            int num = answer + 1;
            if (cnt[num] == 0 || cnt[num] == num) {
                ans += num;
                cnt[num] = 1;
            } else {
                cnt[num]++;
            }
        }
        return ans;
    }
}

下面是题解的代码，思路是如果有 x 只兔子都回答 y，则至少有 x /(y + 1) （向上取整）种不同的颜色，且每种颜色有 y + 1 只兔子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numRabbits(int[] answers) {
        Map<Integer, Integer> count = new HashMap<Integer, Integer>();
        for (int y : answers) {
            count.put(y, count.getOrDefault(y, 0) + 1);
        }
        int ans = 0;
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            int y = entry.getKey(), x = entry.getValue();
            ans += (x + y) / (y + 1) * (y + 1);
        }
        return ans;
    }
}