题目描述给定一个整数数组nums和一个整数k返回其中出现频率前k高的元素。答案可以按任意顺序返回。例如nums [1,1,1,2,2,3], k 2每个元素的出现频率是1 - 3 次 2 - 2 次 3 - 1 次所以返回[1, 2]注意题目要返回的是出现频率最高的元素本身不是它们的出现次数。最初思路一开始的想法是用HashMap统计每个元素出现的次数。把频率取出来排序。取排序后的前k个结果。这个方向里统计频率这一步是对的MapInteger, Integer m new HashMap(); for (int num : nums) { m.merge(num, 1, Integer::sum); }但后面如果只把value放进数组排序最后得到的是频率不是元素本身。比如nums [1,1,1,2,2,3], k 2频率数组是[3, 2, 1]取前两个会得到[3, 2]但正确答案应该是[1, 2]问题出在哪里这道题最容易混淆的是Map里的key和valuekey - 元素本身 value - 出现频率题目要求返回的是key只是排序依据是value。所以不能只对频率排序然后把频率放进答案数组。真正要做的是根据频率找到对应的元素。后来改成桶排序时又出现了几个细节问题new ArrayList[maxCnt 1]只创建了数组每个桶还没有初始化。从高频往低频遍历时循环条件不能写成i k因为i表示频率不表示已经取了几个元素。同一个频率下可能有多个元素放入ans前要判断是否已经取满k个。正确思路可以用桶排序来做。核心思想是频率最大不会超过nums.length所以可以创建一个桶数组让下标表示频率。buckets[频率] 这个频率下的所有元素例如nums [1,1,1,2,2,3]统计频率后1 - 3 2 - 2 3 - 1放入桶中buckets[3] [1] buckets[2] [2] buckets[1] [3]然后从最高频率开始往低频率遍历依次把元素放进答案数组直到取满k个。关键不变量桶排序过程中要始终保持buckets[cnt] 里存放的都是出现次数为 cnt 的元素答案收集过程中要始终保持j 表示 ans 中已经放入的元素个数所以外层循环要看频率i内层填答案时要看j k。手推过程以这个例子为例nums [1,1,1,2,2,3], k 2第一步统计频率1 - 3 2 - 2 3 - 1第二步放入桶buckets[3] [1] buckets[2] [2] buckets[1] [3]第三步从高频到低频取元素i 3取出 1ans [1] i 2取出 2ans [1, 2]此时已经取满k 2个元素直接结束。边界处理需要特别注意同频元素的情况。比如nums [1,1,2,2,3], k 1频率最高的是1 - 2 2 - 2此时buckets[2] [1, 2]但答案数组只需要放 1 个元素。如果内层循环不判断j k就可能继续写入第二个元素导致数组越界。因此内层循环也要限制for (int x : buckets[i]) { if (j k) { break; } ans[j] x; }伪代码创建 HashMap freq 遍历 nums: freq[num] 找到最大频率 maxCnt 创建 buckets长度为 maxCnt 1 初始化每一个桶 遍历 freq: num entry.key cnt entry.value buckets[cnt].add(num) 创建答案数组 ans j 0 从 maxCnt 遍历到 1: 遍历 buckets[i] 中的元素: 如果 j k: 停止 ans[j] 当前元素 j 返回 ansJava 代码class Solution { public int[] topKFrequent(int[] nums, int k) { MapInteger, Integer freq new HashMap(); for (int num : nums) { freq.merge(num, 1, Integer::sum); } int maxCnt Collections.max(freq.values()); ListInteger[] buckets new ArrayList[maxCnt 1]; for (int i 0; i maxCnt; i) { buckets[i] new ArrayList(); } for (Map.EntryInteger, Integer entry : freq.entrySet()) { int num entry.getKey(); int cnt entry.getValue(); buckets[cnt].add(num); } int[] ans new int[k]; int j 0; for (int i maxCnt; i 1 j k; i--) { for (int num : buckets[i]) { if (j k) { break; } ans[j] num; } } return ans; } }易错点题目返回的是元素本身不是出现次数。Map.Entry中getKey()是元素getValue()是频率。ListInteger[] buckets new ArrayList[maxCnt 1]后每个桶还需要初始化。外层循环应该从maxCnt往1遍历不是和k比较频率。同一个频率可能对应多个元素写入答案前要防止超过k个。Lambda 参数不要写_在较新的 Java 版本中_不能作为变量名。建议测试用例nums [1,1,1,2,2,3], k 2 期望[1,2]nums [1], k 1 期望[1]nums [1,1,2,2,3], k 1 期望[1] 或 [2]nums [4,1,-1,2,-1,2,3], k 2 期望[-1,2] 或 [2,-1]复杂度分析设数组长度为n不同元素个数为m。统计频率需要O(n)。建桶需要O(m)。从高频到低频取答案最多遍历所有不同元素时间是O(m)。所以总时间复杂度是O(n)桶数组和哈希表需要额外空间O(n)总结这道题的关键不是“怎么排序频率”而是“如何根据频率找到对应的元素”。HashMap负责建立元素和频率的关系桶排序负责把相同频率的元素归类。最后从高频桶往低频桶收集元素就能得到前k个高频元素。下次再写这题时可以先问自己我最后放进答案的是key还是value桶数组里的每个ArrayList初始化了吗外层循环控制的是频率还是答案数量如果一个桶里有多个元素答案数组会不会越界