前往
大廳
主題

LeetCode - 692. Top K Frequent Words 解題心得

Not In My Back Yard | 2023-05-29 12:00:15 | 巴幣 0 | 人氣 132

題目連結:


題目意譯:
給定一個字串陣列 words 以及一個整數 k,回傳 k 個出現最頻繁的字串。

將答案以出現頻率由高到低排後回傳。同一個頻率的字串們應按照字典序排序。

限制:
1 ≦ words.length ≦ 500
1 ≦ words[i].length ≦ 10
words[i] 由小寫英文字母組成。
k 位於範圍 [1, words 中的字串種類數]。

進階: 你可以時間複雜度 O(n log(k)) 以及額外空間複雜度 O(n) 解開本題嗎?



範例測資:
範例 1:
輸入: words = ["i","love","leetcode","i","love","coding"], k = 2
輸出: ["i","love"]
解釋: "i" 和 "love" 為兩個出現最頻繁的字詞。
注意到 "i" 排於 "love" 之前,因為前者有著較小的字典序。

範例 2:
輸入: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
輸出: ["the","is","sunny","day"]
解釋: "the" 、 "is" 、 "sunny" 和 "day" 為四個出現最頻繁的字詞,其依序的出現次數為 4 、 3 、 2 和 1 次。


解題思維:
先利用一個雜湊表(Hash Table)來統計每一種字詞的出現次數。

接著就是單純地使用一個優先佇列(Priority Queue)來保留前 k 常出現的字詞即可。最後把這 k 個字詞依序排出來即可。




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

創作回應

更多創作