Leetcode 781. rabbit hash table in forest / mathematical problem medium

---

1.Description

In the forest , Every rabbit has a color . Some of the rabbits （ It could be all ） Tell you how many other rabbits have the same color as themselves . We put these answers in answers In the array .

Return to the minimum number of rabbits in the forest .

---

2.Example

 Example :
 Input : answers = [1, 1, 2]
 Output : 5
 explain :
 Two answered  "1"  The rabbit of may have the same color , Set it to red .
 Then I answered  "2"  The rabbit is not red , Otherwise their answers will contradict each other .
 Let's answer  "2"  The rabbit is blue .
 Besides , There should be something else in the forest  2  Only the blue rabbit's answer is not included in the array .
 So the minimum number of rabbits in the forest is  5: 3  Only answers and  2  There is no answer .

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

 Input : answers = []
 Output : 0

---

3.Solution

1. My explanation

Use an array to count the numbers that rabbits say ,a,b You can deduce the meaning of , for instance 2 The rabbit has 4 individual , Then at least there is 3 The two rabbits are the same color ,a It means how many colors there are ,b It means that there are two other rabbits with the same color as it .

class Solution {
    
    public static int numRabbits(int[] answers) {
    
        int[] nums = new int[1000];
        for(int i=0;i<answers.length;i++) {
    
        	nums[answers[i]]++;
        }
        int sum = 0;
        for(int i=0;i<answers.length;) {
    
        	if(nums[answers[i]]!=-1&&nums[answers[i]]>(answers[i]+1)) {
    
        		int a = nums[answers[i]]/(answers[i]+1);
        		int b = nums[answers[i]]%(answers[i]+1);
        		sum += a*(answers[i]+1);
        		if(b!=0) {
    
        			sum += answers[i]+1;
        		}
        	}else if(nums[answers[i]]!=-1&&nums[answers[i]]<=(answers[i]+1)){
    
                sum += answers[i]+1;
            }
            // Set the calculated number to a number that will not be used -1, It is convenient to skip it when traversing 
        	nums[answers[i]] = -1;
        	while(i<answers.length&&nums[answers[i]]==-1) {
    
        		i++;
        	}
        }
        return sum;
    }
}

2. official

A hash table is used to count rabbits . Round up to round down ：

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();
            // Convert rounding up to rounding down , See the picture for the certificate 
            ans += (x + y) / (y + 1) * (y + 1);
        }
        return ans;
    }
}