本文共 1881 字,大约阅读时间需要 6 分钟。
返回森林中兔子的最少数量。
示例:
输入: answers = [1, 1, 2] 输出: 5 解释: 两只回答了 “1” 的兔子可能有相同的颜色,设为红色。 之后回答了 “2” 的兔子不会是红色,否则他们的回答会相互矛盾。 设回答了 “2” 的兔子为蓝色。 此外,森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。 因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。输入: answers = [10, 10, 10]
输出: 11输入: answers = []
输出: 0 说明:answers 的长度最大为1000。
answers[i] 是在 [0, 999] 范围内的整数。两种情况:
1、同种颜色的兔子所回应的数量一定是相同的 2、有可能有不同颜色的兔子回应了同样的数量 思路: 先对数组进行排序,利用哈希表保存回应相同数量的兔子的数量。 1、若 value(回应的兔子数量)等于 key(回应的数量)+ 1 ,意味着这个颜色的兔子全部都回应了; 2、若 value 大于 key + 1,则意味着有不同颜色的兔子回应了相同的数量; 3、若 value 小于 key + 1,则意味着该颜色的兔子并没有全部回应 具体代码如下import java.util.Map.Entry;class Solution { public static int numRabbits(int[] answers) { if( answers.length == 0 ) return 0; // 如果没有任何回应,则返回0 Arrays.sort(answers); int count = 0; Mapmap = new HashMap (); int loc = 0; // 保存该回应数量的开始位置 for( int i = 1; i < answers.length; i++) { if( answers[i] != answers[i-1] ) { // 此时的 i 指向的是下一回应数量的位置 map.put(answers[i-1], i - loc); loc = i; } } map.put(answers[answers.length-1], answers.length - loc); Set > set = map.entrySet(); for( @SuppressWarnings("rawtypes") Entry entry : set ){ // 注:key + 1 代表该颜色的兔子总共拥有的数量 int key = (int)entry.getKey(); int value = (int)entry.getValue(); if( value == key + 1 ) { // 如果该颜色的兔子全部都回应了 count += (int)entry.getValue(); // 直接相加 } else { if( value < key + 1 ) { // 如果该颜色的兔子没有全部回应 count += key + 1; } else if( value > key + 1 ) { // 如果有其他颜色的兔子也回应相同的数量 while( value > key + 1 ) { count += key + 1; value -= key + 1; } count += key + 1; } } } return count; }}
转载地址:http://ploe.baihongyu.com/