LeetCode Top K高频元素问题：为何需遍历keySet而非nums数组？

这是LeetCode上的「Top K Frequent Elements」问题，要求返回出现频率前K高的元素。标准桶排序解法中，统计完元素频率后需要遍历map的keySet来填充桶，但如果替换成遍历原nums数组填充桶，会得到错误答案，原因如下：

代码对比 #

正确的遍历keySet代码 #

for(int n : map.keySet()) {
    int freq = map.get(n);
    if(bucket[freq] == null) {
        bucket[freq] = new ArrayList<Integer>(); 
    }
    bucket[freq].add(n); 
}

错误的遍历nums数组代码 #

for(int n : nums) {
    int freq = map.get(n);
    if(bucket[freq] == null) {
        bucket[freq] = new ArrayList<Integer>(); 
    }
    bucket[freq].add(n); 
}

核心错误原因 #

遍历nums数组时，同一个元素会被重复添加到对应频率的桶中。因为nums数组里每个元素的出现次数等于它的频率，遍历过程中该元素会被处理多次，导致桶中出现大量重复元素。

举个实际例子：假设nums为[1,1,2,2,3]，map中1的频率是2、2的频率是2、3的频率是1：

• 遍历keySet时，桶bucket[2]只会添加1和2各一次，最终是[1,2]，后续收集前K个高频元素时能得到正确的去重结果。
• 遍历nums时，桶bucket[2]会被添加1两次、2两次，变成[1,1,2,2]，收集前2个元素时可能取出两个1，完全不符合题目要求的“返回前K个高频元素（每个元素仅需出现一次）”。

这种重复添加会导致最终结果包含大量重复元素，无法满足题目对输出的要求，因此必须遍历map的keySet来确保每个元素只被添加一次。

内容的提问来源于stack exchange，提问作者Ramkrishna Sharma