Python3自定义排序

  |  

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

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


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

$1 自定义排序

在 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 的排序规则一般写成函数(或者可调用对象)。

代码: 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 中这参数 cmp 取消了,但是还是可以通过 key 参数实现自定义排序。调用时,参数 key 可以指定一个带参数的函数 mykey,mykey 返回 list 元素用于比较的 key,这个 key 实现了 __lt__ 等特殊方法。

代码: python3 风格自定义比较函数

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

l.sort(key=mykey)

通过 functools.cmp_to_key(mycmp) 可以将 python2 的 mycmp 变成 mykey。

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

代码: cmp_to_key 的实现

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

$2 题目

506. 相对名次

问题

给出 N 名运动员的成绩,找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”,“银牌” 和“ 铜牌”(”Gold Medal”, “Silver Medal”, “Bronze Medal”)。

(注:分数越高的选手,排名越靠前。)

代码

  • 定义 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
  • 直接定义 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