Python3自定义排序:直接定义键函数,或先定义比较函数再转换为键函数

  |  

摘要: Python 3 中如何实现自定义排序

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


自定义排序是算法中很常见的一个操作,参考自定义排序

$1 自定义排序

比较函数:Python2 风格

在 Python2 中,sort 和 sorted 可以通过参数 cmp 指定排序规则。

1
2
3
# python list 排序接口,直接在本地排序
list.sort(cmp=None, key=None, reverse=False) # Python2
list.sort(key=None, reverse=False) # Python3

其中 python2 的排序规则一般写成比较函数(或者可调用对象)。

1
2
3
4
5
6
7
8
9
def mycmp(x, y):
if x.key < y.key:
return -1
elif x.key > y.key:
return 1
else:
return 0

l.sort(cmp=mycmp)

键函数: python3 风格

Python3 中参数 cmp 取消了,但是还是可以通过 key 参数实现自定义排序。调用时,参数 key 可以指定一个带参数的键函数 mykey,mykey 返回 list 元素用于比较的 key,这个 key 实现了 __lt__ 等特殊方法。

下面的例子中,mykey 是键函数,x 为 list 元素,键函数返回该元素用于比较的 key,也就是 x.keyx.key 是需要带有 __lt__ 等方法的。

1
2
3
4
def mykey(x):
return x.key

l.sort(key=mykey)

cmp_to_key:比较函数转键函数

通过 functools.cmp_to_key(mycmp) 可以将 python2 的 mycmp 变成 mykey。代码如下:

1
l.sort(key=cmp_to_key(mycmp))

cmp_to_key 的实现

cmp_to_key 将比较函数转换为键函数。也就是键函数中的 __lt__ 等方法依据比较函数 mycmp 来实现。

大致的代码如下,其中 obj 代表一个 list 元素,返回的类 K 就是用于比较的键(事实上就可以理解为 obj 本身,只是给它加上了 __lt__ 等函数,所以可以理解 K 是 obj 的一个 Wrapper),其中的 __lt__ 是根据 mycmp 函数定义的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

这里的 __slots__ 是一个类属性,它用于限制实例属性的数量,从而节省内存。当你在类定义中使用 __slots__ 时,即可明确指定该类实例将具有的属性列表。

总结

总结一下,Python3 中 sort 函数对列表 l 排序,列表元素 x 可能没有 __lt__,这样 l 本身就不能排序;也可能 x__lt__ 但是不是我们想要的逻辑。此时想要给 l 排序,一个最直接的办法是给 x 对象自定义一个 __lt__,这样 x 本身就可以支持按给定逻辑排序。

也可以通过给 sort 函数的 key 参数传递一个键函数的方式来做 key 参数接收一个可调用对象 mykeymykey 在调用时接收一个参数 x 也就是 list 中的元素(这个元素 x 可能没有 __lt__,或者有 __lt__ 但不是我们想要的逻辑。)。mykey(x) 返回一个将 x 包装后的对象,代表用于比较 list 元素的键,而这个所谓的键其实就是 x 本身,只是给他增加了 __lt__ 等函数。所以其实质还是相当于给 x 对象自定义了 __lt__

对于简单的情况,例如用于比较 list 元素的键就是元素的某个属性,且该属性是 int 等基本类型,自带了 __lt__,那么写法就很简单,参考前面【键函数:Python3 风格】这一小节的代码。

如果复杂情况,比如比较 list 元素时涉及到多个属性,或者某个属性没有自带 __lt__ 需要自己实现。那么可以先将比较的逻辑写在比较函数 mycmp 中,然后通过 cmp_to_key 转换为一个类包装器,作为 mykey


$2 题目:506. 相对名次

给你一个长度为 n 的整数数组 score ,其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都 互不相同 。

运动员将根据得分 决定名次 ,其中名次第 1 的运动员得分最高,名次第 2 的运动员得分第 2 高,依此类推。运动员的名次决定了他们的获奖情况:

  • 名次第 1 的运动员获金牌 “Gold Medal” 。
  • 名次第 2 的运动员获银牌 “Silver Medal” 。
  • 名次第 3 的运动员获铜牌 “Bronze Medal” 。
  • 从名次第 4 到第 n 的运动员,只能获得他们的名次编号(即,名次第 x 的运动员获得编号 “x”)。

使用长度为 n 的数组 answer 返回获奖,其中 answer[i] 是第 i 位运动员的获奖情况。

提示:

1
2
3
4
n == score.length
1 <= n <= 1e4
0 <= score[i] <= 1e6
score 中的所有值 互不相同

示例 1:
输入:score = [5,4,3,2,1]
输出:[“Gold Medal”,”Silver Medal”,”Bronze Medal”,”4”,”5”]
解释:名次为 [1st, 2nd, 3rd, 4th, 5th] 。

示例 2:
输入:score = [10,3,8,9,4]
输出:[“Gold Medal”,”5”,”Bronze Medal”,”Silver Medal”,”4”]
解释:名次为 [1st, 5th, 3rd, 2nd, 4th] 。

代码(Python),先定义比较函数,再转换为键函数

  • 定义 python2 风格的比较函数,再通过 functools.cmp_to_key 转换为 python3 的提取 key 的键函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from functools import cmp_to_key

class Cmp:
def __init__(self, nums):
self.nums = nums

def __call__(self, i, j):
if self.nums[i] > self.nums[j]:
return -1
if self.nums[i] < self.nums[j]:
return 1
return 0


class Solution:
def findRelativeRanks(self, nums: List[int]) -> List[str]:
n = len(nums)
indexes = [i for i in range(n)]
mycmp = Cmp(nums)
indexes.sort(key=cmp_to_key(mycmp))
result = ["" for _ in range(n)]
for i, idx in enumerate(indexes):
if i == 0:
result[idx] = "Gold Medal"
elif i == 1:
result[idx] = "Silver Medal"
elif i == 2:
result[idx] = "Bronze Medal"
else:
result[idx] = str(i + 1)
return result

代码(Python),直接定义键函数

  • 直接定义 python3 的提取 key 的函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Key:
def __init__(self, nums):
self.nums = nums

def __call__(self, i):
return self.nums[i]


class Solution:
def findRelativeRanks(self, nums: List[int]) -> List[str]:
n = len(nums)
indexes = [i for i in range(n)]
mykey = Key(nums)
indexes.sort(key=mykey, reverse=True)
result = ["" for _ in range(n)]
for i, idx in enumerate(indexes):
if i == 0:
result[idx] = "Gold Medal"
elif i == 1:
result[idx] = "Silver Medal"
elif i == 2:
result[idx] = "Bronze Medal"
else:
result[idx] = str(i + 1)
return result

Share