In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those
answers are placed in an array.
Return the minimum number of rabbits that could be in the forest.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int numRabbits(int[] answers) { | |
| // filter abnormal cases | |
| if (answers == null || answers.length == 0) { | |
| return 0; | |
| } | |
| if (answers.length == 1) { | |
| return answers[0] + 1; | |
| } | |
| int answer = 0; | |
| HashMap<Integer, Integer> map = new HashMap<>(); | |
| for (int key : answers) { | |
| if (!map.containsKey(key)) { | |
| map.put(key, 1); | |
| } else { | |
| map.put(key, map.get(key) + 1); | |
| } | |
| } | |
| for (Map.Entry<Integer, Integer> integerIntegerEntry : map.entrySet()) { | |
| int key = integerIntegerEntry.getKey(); | |
| int val = integerIntegerEntry.getValue(); | |
| if (val % (key + 1) == 0) { | |
| answer += val; | |
| } else { | |
| answer += (val / (key + 1) + 1) * (key + 1); | |
| } | |
| } | |
| // return the final result | |
| return answer; | |
| } | |
| } |
No comments:
Post a Comment