781. Rabbits in the forest

This is the 23rd day of my participation in the August More Text Challenge.More challenges in August

In the forest, every rabbit has a color. Some of them (maybe all of them) tell you how many other rabbits have the same color. We put these answers in the ANSWERS array.

Returns the minimum number of rabbits in the forest.

Example: Input: Answers = [1, 1, 2] Output: 5 Explanation: Two rabbits that answered “1” might have the same color. Set it to red. Rabbits that later answered “2” would not be red, or their answers would contradict each other. Let the rabbit that answers “2” be blue. In addition, there should be 2 other blue rabbits in the forest whose answers are not included in the array. So the minimum number of rabbits in the forest was 5: 3 that answered and 2 that didn’t.

Input: Answers = [10, 10, 10] Output: 11

Input: answers = [] Output: 0

Their thinking

Two rabbits of the same color must see the same number of other rabbits of the same color. Conversely, if two rabbits see different numbers of other rabbits of the same color, they will be different colors.

If there are three white rabbits, each of them must answer “2”; But if one of the rabbits answered 2, it could be just three rabbits, or it could be three rabbits and three gray rabbits

Therefore, if a group of rabbits of the same type are reported and the array is traversed once, how many rabbits are missing in each group can be known, plus the number of rabbits in the original array, which is the minimum number of rabbits in the forest.

code

class Solution {
    public int numRabbits(int[] answers) {

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < answers.length; i++) {
            if(answers[i]==0) continue; // Unique rabbit
            map.put(answers[i],map.getOrDefault(answers[i],answers[i]+1) -1);
            if(map.get(answers[i])==0) map.remove(answers[i]);// This group has been removed
        }
        int res=answers.length;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            res+=entry.getValue();
        }
        returnres; }}Copy the code

Time complexity: O(n), where n is the length of the array ANSWERS.

Space complexity: O(n). In the worst case, the hash table has n elements.

781. Rabbits in the forest