題目出處
難度
medium
個人範例程式碼 – 單 hashtable + 自定義排序 key function
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
word_to_counter = defaultdict(int)
counter_to_word = defaultdict(list)
# O(N)
for word in words:
word_to_counter[word] += 1
word_list = [(word, cnt) for word, cnt in word_to_counter.items()]
word_list.sort(key = self.key_function)
return [word_list[i][0] for i in range(k)]
def key_function(self, word_tuple):
# first compare: cnt (biggest need first, so we use -cnt: 4, 5 -> -5, -4)
# second compare: word alphabetically first (lexicographical)
word, cnt = word_tuple
return (-cnt, word)
return 那行使用的 list comprehension,同義於下方程式碼
return 那行優化後,我才寫成上面一行的形式,
原本的內容長下面那樣,
基本上面試時,建議以自己較能掌握的穩定寫法為主。
ans = []
for i in range(k):
ans.append(word_list[i][0])
return ans
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
算法說明
另外一個方法是我們一樣用 hashtable 先把所有數量都數出來,
可以想像做我們把所有的 word 變成 (word, count) 的形式,
再來我們要使用自定義排序,排成我們要的順序。
自定義排序 key function
一般來說,sort 都是幫我們單純直接照「數字大小排序」或是「照字母大小排序」,
但在這題目當中,我們需要同時「先考慮數字大小,再考慮字母順序」,
因此這樣的情況我們需要去特別定義排序的規則。
我們可以自己寫一個 key_fuction 給 key 去使用,
回傳一個 tuple 給 key 參考,
依照 tuple 的順序,就是我們比較的順序。
依照題目要的,數量越大的排序要越前面,因此我們排序結果應該要是
「5,4,3,2,1」(反序),再來「照字母順序 a,b,c 排」(升序)
相對簡單的處理方式是,我們就直接讓數字前面加一個「負號」,
這樣「-5,-4,-3,-2,-1」就是升序的排列了!
因此我們回傳 (-cnt, word) 作為我們排序的依據。
word_list.sort(key = self.key_function)
def key_function(self, word_tuple):
# first compare: cnt (biggest need first, so we use -cnt: 4, 5 -> -5, -4)
# second compare: word alphabetically first (lexicographical)
word, cnt = word_tuple
return (-cnt, word)
input handling
x
Boundary conditions
用 for 來控制範圍
個人範例程式碼 – 雙 hashtable 紀錄 word_to_counter, counter_to_word
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
word_to_counter = defaultdict(int)
counter_to_word = defaultdict(list)
# O(N)
for word in words:
word_to_counter[word] += 1
current_word_count = word_to_counter[word]
if current_word_count > 1: # existed word
counter_to_word[current_word_count-1].remove(word)
counter_to_word[current_word_count].append(word)
# O(nlogN)
counter_keys = sorted(counter_to_word.keys(), reverse=True)
ans = []
cnt = 0
for key in counter_keys:
if cnt >= k:
break
ans += sorted(counter_to_word[key])
cnt += len(counter_to_word[key])
return ans[:k]
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
算法說明
第一次看到這題目,想說都要計數了,然後還要排序,直覺就想說用兩個 hashtable,
分別存 word_to_counter, counter_to_word,
當存到 k 個的時候,就輸出結果。
排序算是純以”數字”為最優先儲存,再處理字母順序。
但我們要注意,這題目有特別說明,取前 k 的時候,「有可能同數量,這時候我們就照字母順序取」
input handling
x
Boundary conditions
用 for 來控制範圍
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||