前往
大廳
主題

LeetCode - 347. Top K Frequent Elements 解題心得

Not In My Back Yard | 2022-08-12 12:00:11 | 巴幣 0 | 人氣 356

題目連結:


題目意譯:
給定一整數陣列 nums 以及一整數 k,回傳前 k 個出現頻率最高的元素。你可以按任意順序回傳答案。

限制:
1 ≦ nums.length ≦ 10 ^ 5
k 位於範圍 [1, 陣列中的相異元素總數量]。
保證答案唯一。
 
進階:你的演算法的時間複雜度必須比 O(n log n) 好,其中 n 為陣列的大小。



範例測資:
範例 1:
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]

範例 2:
輸入: nums = [1], k = 1
輸出: [1]


解題思維:
首先統計一次每種數字的出現次數(可以使用雜湊表(Hash Table))。而因為出現次數必定被陣列大小 n 所限制住(也就是介於 0 ~ n 之間),所以我們把每一種可能的出現次數(也就是 0 ~ n)都列出來哪些數字的出現次數符合對應的位置(例如說如果 5 和 7 都出現了 2 次,則索引值 2 的位置要塞 5 和 7 這兩個元素)。

因此我們就從出現次數 n 掃到 0,然後在路途上挑出 k 個元素即是出現頻率最高的 k 個元素,即所求。

而時間複雜度為 O(n)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作