Re: [問題] sorting cmp_to_key

看板Python作者suhang (suhang)時間7年前發表 (2018/02/20 22:51), 7年前編輯推噓4(4推 0噓 15→)

留言19則, 5人參與, 7年前最新討論串3/3 (看更多)

原題 http://www.lintcode.com/en/problem/word-sorting/ 這題不知道該怎麼用單純的key去解，所以才想用comparator 不然就得手動寫一個merge sort之類的 my solution in Python3 from functools import cmp_to_key class Solution: """ @param alphabet: the new alphabet @param words: the original string array @return: the string array after sorting """ def wordSort(self, alphabet, words): # Write your code here myord = {} rank = {} for i, c in enumerate(alphabet): myord[c] = i def mycmp(a, b): length = min(len(a), len(b)) for i in range(length): if a[i] != b[i]: return myord[a[i]] - myord[b[i]] return len(a) - len(b) words.sort(key = cmp_to_key(mycmp)) return words ※ 引述《uranusjr (←這人是超級笨蛋)》之銘言： : ※ 引述《suhang (suhang)》之銘言： : : https://stackoverflow.com/questions/10645986/custom-sort-python : : 我想將 : : key = lambda word: [alphabet.index(c) for c in word[0]] : : 這行轉換成老式cmp function : : def mycmp(a, b): : : return a - b : : sorted(words, key = cmp_to_key(mycmp)) : : 但是不太會寫 : : 請大家提示一下 a, b分別該是什麼? 謝謝 : cmp 與 key 的寫法邏輯完全不一樣 : 直接轉換基本上是行不通的, 重寫比較快 : 你必須要仔細想一下你的比對邏輯到底是什麼, 才能寫出正確的比較函式 : key 函式是把本來不能比較（或比較法和你想的不同）的東西轉換成可比較的東西 : 接著再用轉換過的東西排序 : 例如你想把 ['apple', 'orange', 'pear'] 用字串長度排列 : 就會把它們轉成字串長度 [5, 6, 4], 排序成 [4, 5, 6] 再轉回來 : 那個轉換函式就是 key 函式, 在這個例子就是取字串長度的 len() : cmp 函式則是會一次給你兩個輸入 a, b 讓你比大小 : 如果 a < b 回傳負數, a > b 正數, 相等回 0 : 同樣用上面的例子, 如果 a = 'apple', b = 'orange' 就要回負數 : 因為 len('apple') < len('orange) : 在這個狀況中, 有個簡單的通解可以達成目的 : def cmp_strs(a, b): : return len(a) - len(b) : 你把可能的三個輸入代進去, 應該就能知道為什麼 : 如同推文提到, cmp 函式並不是特別優秀的功能 : 從上面的例子也可以看出來, cmp 函式的實作方法相對不直覺 : 根據你想要實作的比較, 甚至可能需要很精明的程式碼, 需要另外註解來解釋 : 除非你需要支援非常舊（不支援 key）的 Python 版本 : 否則幾乎永遠不應該寫 cmp 函式, 而應該使用更簡潔易懂的 key 函式 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 8.41.187.50 ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1519167083.A.984.html ※ 編輯: suhang (8.41.187.50), 02/21/2018 06:51:59

推

vfgce

02/21 07:50, 7年前 , 1^F

02/21 07:50, 1^F

→

vfgce

02/21 07:50, 7年前 , 2^F

02/21 07:50, 2^F

推

vfgce

02/21 07:53, 7年前 , 3^F

02/21 07:53, 3^F

→

vfgce

02/21 07:53, 7年前 , 4^F

02/21 07:53, 4^F

→

vfgce

02/21 07:54, 7年前 , 5^F

02/21 07:54, 5^F

一開始comparator寫不出來，這篇只是單純分享我的解法但是我覺得純用key funcion應該解不出這題有人有想法嗎? 如果用 words.sort(key = lambda word: [alphabet.index(c) for c in word[0]]) 下面這個case會fail input: alphebet = "zbadefghijklmnopqrstuvwxyc" words = ["bca","czb","za","zba","ade"] return ["za","zba","bca","ade","czb"] expect ["zba","za","bca","ade","czb"] ※ 編輯: suhang (8.41.187.50), 02/21/2018 08:16:49

推

vfgce

02/21 08:35, 7年前 , 6^F

02/21 08:35, 6^F

→

vfgce

02/21 08:35, 7年前 , 7^F

02/21 08:35, 7^F

→

vfgce

02/21 08:36, 7年前 , 8^F

02/21 08:36, 8^F