題目描述給定一個整數數組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初始化了嗎外層循環控制的是頻率還是答案數量如果一個桶里有多個元素答案數組會不會越界