为什么遍历HashMap的keySet统计数组最高频数字会得到错误输出?
问题描述
给定以下统计数组最高频率数字的Java实现:
public static int maxFrequencyNumber(int[] arr){ /* Your class should be named Solution * Don't write main(). * Don't read input, it is passed as function argument. * Return output and don't print it. * Taking input and printing output is handled automatically. */ HashMap<Integer, Integer> map = new HashMap<>(); for(int i : arr) { if(map.containsKey(i)) { map.put(i, map.get(i) + 1 ); }else { map.put(i, 1); } } int maxFreq = 0; int max = Integer.MIN_VALUE; for(int i : map.keySet()){ if( maxFreq < map.get(i) ) { maxFreq = map.get(i); max = i; } } return max; }
该实现遍历HashMap的keySet()统计最高频率数字时会出现部分错误,改为遍历原数组则结果全部正确。
错误原因
- 未处理多数字同最高频率的边界场景:当数组中存在两个及以上的数字出现频率相同且均为最高值时,该题的隐含要求是返回在原数组中最先出现的那个数字,现有逻辑无法满足该要求。
- HashMap的
keySet()不保留插入顺序:Java标准库的HashMap不会记录元素的插入先后顺序,遍历keySet()时,同频率的多个数字的遍历顺序是不确定的,只有当频率严格大于当前记录的最高频率时才会更新返回值,最终返回的是最后一个被遍历到的同最高频率数字,和要求的「最先出现」规则冲突。
举个简单的测试用例:数组为[2,3,3,2],2和3的出现频率都是2(最高频率)。遍历keySet()时可能先遍历到3,也可能先遍历到2,最终返回值不确定;如果改为遍历原数组,先遇到2时会将最高频率设为2、返回值设为2,后续遇到3时因为频率等于当前最高频率不会触发更新,最终返回2,符合题目要求。
修复方案
如果要保留遍历HashMap的实现方式,可以额外新增一个HashMap记录每个数字第一次出现的下标,遍历keySet()时如果遇到频率相同的数字,比较两者的首次出现下标,返回下标更小的即可。如果无需优化时间复杂度,直接改为遍历原数组统计即可。
内容的提问来源于stack exchange,提问作者Codered
相关产品推荐
相关产品推荐

