1. 題目描述

題目中轉：347. 前 K 個高頻元素

2.詳細題解

? ? 尋找出現頻率前$k$高的元素，因此需要先統計各個元素出現的次數，該步驟時間復雜度為$O(n)$，再對各元素的出現頻率進行排序，假定不同元素的個數為$m$，該步驟的最佳時間復雜度為$O(mlog(m))$，如歸并、堆排序等算法。
??這里介紹一種桶排序算法：桶排序（Bucket Sort）是一種排序算法，它通過將數據分散到有限數量的桶中，然后對每個桶中的數據單獨進行排序，最后按照順序將各個桶中的數據合并起來得到最終排序結果。簡單的說，已知數據種類有限，逐一遍歷數據并裝入相應的桶中，僅需$O(n)$時間復雜度即可完成數據排序。
??對于本題，先統計各元素出現的頻率，再以元素的頻率作為桶，將相應頻率的元素放入指定桶中。具體算法如下：

• Step1：初始化：統計各元素出現的頻率，數據結構為字典，算法時間復雜度為$O(n)$；
• Step2：數組中元素個數為$n$，構建$n+1$個桶，數據結構為數組，數組的索引下標對應元素出現的頻率（可進一步優化，桶的數據為元素出現的最大頻率）；
• Step3：遍歷各元素出現的頻率，放入對應桶中，算法時間復雜度為$O(m)$；
• Step4：從右至左遍歷桶，如果桶中有元素，則放入最終結果：
• Step5：當結果數量為$k$時，程序結束；
• Step8：返回結果。

3.代碼實現

3.1 Python

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:fre_dict = {}for num in nums:fre_dict[num] = fre_dict.get(num, 0) + 1res = [[] for _ in range(len(nums) + 1)]for key, value in fre_dict.items():res[value].append(key)ans = []for i in range(len(nums), 0, -1):if len(res[i]) > 0:ans.extend(res[i])if len(ans) == k:breakreturn ans

3.2 Java

class Solution {public int[] topKFrequent(int[] nums, int k) {int[] res = new int[k];HashMap<Integer, Integer> fre_dict = new HashMap();for (int num: nums){if (fre_dict.containsKey(num)){fre_dict.put(num, fre_dict.get(num)+1);}else {fre_dict.put(num, 1);}}List<Integer>[] list = new List[nums.length+1];for(int key : fre_dict.keySet()){// 獲取出現的次數作為下標int i = fre_dict.get(key);if(list[i] == null){list[i] = new ArrayList();} list[i].add(key);}for (int i=list.length-1, j = 0; i>=0 && j < k; i--){if (list[i] == null) continue;for (int value: list[i]){res[j++] = value;}}return res;}
}

??執行用時不必過于糾結，對比可以發現，對于python和java完全相同的編寫，java的時間一般是優于python的；至于編寫的代碼的執行用時擊敗多少對手，執行用時和網絡環境、當前提交代碼人數等均有關系，可以嘗試完全相同的代碼多次執行用時也不是完全相同，只要確保自己代碼的算法時間復雜度滿足相應要求即可，也可以通過點擊分布圖查看其它coder的code。