作者suhang (suhang)
看板Python
標題Re: [問題] sorting cmp_to_key
時間Wed Feb 21 06:51:21 2018
原題
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://webptt.com/m.aspx?n=bbs/Python/M.1519167083.A.984.html
※ 編輯: suhang (8.41.187.50), 02/21/2018 06:51:59
1F：推 vfgce: 你自己po的key=lambda word:[alphabet.index(c) for c...] 02/21 07:50
2F：→ vfgce: 這個就可以了.你的問題在那? 02/21 07:50
3F：推 vfgce: 化成list,list的比法就是依序比大小... 02/21 07:53
4F：→ vfgce: 前面幾個都一樣,就看長度,如[1,2]<[1,2,3] 02/21 07:53
5F：→ vfgce: 幹嘛自己刻比較方法? 02/21 07:54
一開始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
6F：推 vfgce: 程式碼要改,for c in word[0]是因為它的資料分兩部分, 02/21 08:35
7F：→ vfgce: 取第一部分來比,你照抄不改當然錯... 02/21 08:35
8F：→ vfgce: 改成for c in word就可以了.... 02/21 08:36
9F：→ vfgce: 你用for c in word[0],只取每個字第一字母,當然錯.... 02/21 08:37
10F：→ suhang: Thanks lambda我很少用，實在不熟 謝謝解釋 02/21 10:15
11F：→ uranusjr: 所以你已經解了, 那你到底想問什麼問題？ 02/21 10:15
12F：→ djshen: 抄別人的好歹去了解一下為什麼這樣寫吧 02/21 10:18
13F：→ djshen: 問題不一樣還照抄 02/21 10:19
14F：推 vfgce: 你對python的資料結構及常用函式還不夠熟,多了解一下list, 02/21 12:21
15F：→ vfgce: tuple,set,dict,str有些什麼東西,該怎麼用..另外,別把其他 02/21 12:22
16F：→ vfgce: 程式語言的想法用在python,取較短序列比較的寫法用 02/21 12:24
17F：→ vfgce: for aa,bb in zip(a,b):來寫即可,多了解一下內建函式, 02/21 12:27
18F：→ vfgce: 忘掉C及java... 02/21 12:27