項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】python – [692] Top K Frequent Words 個人解法筆記 | 內含自定義排序 key function 的使用方法

題目出處

692. Top K Frequent Words

難度

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 SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python