cmp_to_key

入門級(jí)排序

python的列表提供了sort方法己儒，下面是該方法的一個(gè)示例

lst = [(9, 4), (2, 10), (4, 3), (3, 6)]
lst.sort(key=lambda item: item[0])
print(lst)

sort方法的key參數(shù)需要設(shè)置一個(gè)函數(shù)，這個(gè)函數(shù)返回元素參與大小比較的值巾腕，這看起來(lái)沒(méi)有問(wèn)題面睛，但如果想實(shí)現(xiàn)更加復(fù)雜的自定義排序，就不那么容易了尊搬。

高階排序

前面例子的排序規(guī)則是根據(jù)元組里第一個(gè)元素的大小進(jìn)行排序叁鉴，我現(xiàn)在修改規(guī)則，如果元組里第一個(gè)元素是奇數(shù)毁嗦，就用元組里第一個(gè)元素進(jìn)行排序亲茅，如果元組里第一個(gè)元素是偶數(shù)，則用這個(gè)元組里的第二個(gè)元素進(jìn)行大小比較狗准，面對(duì)這樣的需求克锣，列表的sort方法無(wú)法滿足。

對(duì)于這種情形腔长，可以使用 functools.cmp_to_key 來(lái)解決

from functools import cmp_to_key
lst = [(9, 4), (2, 10), (4, 3), (3, 6)]

def cmp(x, y):
    a = x[0] if x[0] %2 == 1 else x[1]
    b = y[0] if y[0] %2 == 1 else y[1]

    return 1 if a > b else -1 if a < b else 0

lst.sort(key=cmp_to_key(cmp))
print(lst)

仍然使用sort進(jìn)行排序袭祟，我實(shí)現(xiàn)了一個(gè)cmp函數(shù)，該函數(shù)實(shí)現(xiàn)了需求中所提到的要求捞附，該函數(shù)最終要返回兩個(gè)元組比較的大小關(guān)系

示例

from functools import cmp_to_key 
L=[9,2,23,1,2]
 
sorted(L,key=cmp_to_key(lambda x,y:y-x))
輸出：
[23, 9, 2, 2, 1]
 
 
sorted(L,key=cmp_to_key(lambda x,y:x-y))
輸出：
[1, 2, 2, 9, 23]

cmp_to_key的實(shí)現(xiàn)

其實(shí)cmp_to_key的實(shí)現(xiàn)非常簡(jiǎn)單

def cmp_to_key(mycmp):
    """Convert a cmp= function into a key= function"""
    class K(object):
        __slots__ = ['obj']
        def __init__(self, obj):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        __hash__ = None
    return K

它在內(nèi)部定義了一個(gè)類K巾乳， 并使用我傳入的cmp函數(shù)完成了比較關(guān)系運(yùn)算符的重載，函數(shù)返回的是一個(gè)類鸟召，而sort函數(shù)的key需要的是一個(gè)函數(shù)胆绊，看起來(lái)矛盾，但在python中欧募，這樣做完全可行压状，因?yàn)轭惡秃瘮?shù)都是callable的，這里把類當(dāng)成了函數(shù)來(lái)用跟继。

在本篇第一段代碼中

lst.sort(key=lambda item: item[0])

lambda表達(dá)式生成的匿名函數(shù)返回的是元組的第一個(gè)元素進(jìn)行大小比較种冬，而現(xiàn)在，cmp_to_key返回的是類K舔糖，參與比較的是K的對(duì)象娱两，由于K已經(jīng)實(shí)現(xiàn)了比較關(guān)系運(yùn)算符重載，且算法就是我剛剛實(shí)現(xiàn)的cmp函數(shù)金吗，這樣就最終實(shí)現(xiàn)了自定義排序十兢。

實(shí)例

力扣題目：179.最大數(shù)

給定一組非負(fù)整數(shù) nums趣竣，重新排列每個(gè)數(shù)的順序（每個(gè)數(shù)不可拆分）使之組成一個(gè)最大的整數(shù)。
注意：輸出結(jié)果可能非常大纪挎，所以你需要返回一個(gè)字符串而不是整數(shù)期贫。

示例 1：
輸入：nums = [10,2]
輸出："210"

示例 2：
輸入：nums = [3,30,34,5,9]
輸出："9534330"

示例 3：
輸入：nums = [1]
輸出："1"

示例 4：
輸入：nums = [10]
輸出："10"

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 109

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/largest-number
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)异袄，非商業(yè)轉(zhuǎn)載請(qǐng)注明出>處通砍。

題目分析

這道題中列表nums中兩個(gè)值的相對(duì)位置并不能由單一num決定，而是說(shuō) x與y拼接比y與x拼接的值大烤蜕，那么就用[x,y]的順序封孙，否則用[y,x]的順序。此時(shí)就是所謂的：?jiǎn)蝹€(gè)元素并沒(méi)有一個(gè)絕對(duì)的大小的情況

代碼

from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums):
        ret = map(str, nums)

        def cmp(a, b):
            if a + b >= b + a:
                return 1
            else:
                return -1
        ret = sorted(ret, key=cmp_to_key(cmp), reverse=True)
        return ''.join(ret) if ret[0] != '0' else '0'