森林中的兔子

力扣 781. 森林中的兔子

题目说明

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

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

提示：
- answers 的长度最大为1000。
- answers[i] 是在 [0, 999] 范围内的整数。

示例

例1

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

例2

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

例3

1 2	输入: answers = [] 输出: 0

笔者理解

此题是一道数学算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题用上哈希表就会比较好解了，我们只需要记录相同伙伴数的个数即可，再依次累加消除即可，让我们来看看具体如何实现的吧。

实现

public int numRabbits(int[] answers) {
        int n = answers.length;
        int result = 0;

        if (n == 0) {
            return result;
        }
        
        Map<Integer, Integer> map = new HashMap();

        // 记录说出相同同伴数的兔子及个数
        for (int i = 0; i < n; i++) {
            if (map.getOrDefault(answers[i], 0) == 0) {
                map.put(answers[i], 1);
            }
            else {
                map.put(answers[i], map.get(answers[i]) + 1);
            }
        }

        int mapKey,mapValue;
        // 遍历各同伴数对应的兔子数，每累计一次兔子数就削减一次相同同伴数的兔子
        for (Map.Entry<Integer, Integer> entry : map.entrySet()){
            mapKey = entry.getKey();
            mapValue = entry.getValue();
            while (mapValue > 0) {
                result += (mapKey + 1);
                mapValue -= (mapKey + 1);
            }
        }

        return result;
    }