347. 前 K 個高頻元素
- 1. 題目描述
- 2.詳細題解
- 3.代碼實現
- 3.1 Python
- 3.2 Java
1. 題目描述
題目中轉:347. 前 K 個高頻元素
2.詳細題解
? ? 尋找出現頻率前 k k k高的元素,因此需要先統計各個元素出現的次數,該步驟時間復雜度為 O ( n ) O(n) O(n),再對各元素的出現頻率進行排序,假定不同元素的個數為 m m m,該步驟的最佳時間復雜度為 O ( m l o g ( m ) ) O(mlog(m)) O(mlog(m)),如歸并、堆排序等算法。
??這里介紹一種桶排序算法:桶排序(Bucket Sort)是一種排序算法,它通過將數據分散到有限數量的桶中,然后對每個桶中的數據單獨進行排序,最后按照順序將各個桶中的數據合并起來得到最終排序結果。簡單的說,已知數據種類有限,逐一遍歷數據并裝入相應的桶中,僅需 O ( n ) O(n) O(n)時間復雜度即可完成數據排序。
??對于本題,先統計各元素出現的頻率,再以元素的頻率作為桶,將相應頻率的元素放入指定桶中。具體算法如下:
- Step1:初始化:統計各元素出現的頻率,數據結構為字典,算法時間復雜度為 O ( n ) O(n) O(n);
- Step2:數組中元素個數為 n n n,構建 n + 1 n+1 n+1個桶,數據結構為數組,數組的索引下標對應元素出現的頻率(可進一步優化,桶的數據為元素出現的最大頻率);
- Step3:遍歷各元素出現的頻率,放入對應桶中,算法時間復雜度為 O ( m ) O(m) O(m);
- Step4:從右至左遍歷桶,如果桶中有元素,則放入最終結果:
- Step5:當結果數量為 k k 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。