leetcode406-python二(多)维list的排序

题目地址在这里
题意不难理解,理解后解法也很快能想出来,就是一个对二维数组排序后再进行遍历插入的操作。这里的排序是按子list的第一个元素的逆序排序,第一个元素相同时,按第二个元素的升序排。实现的时候有一个疑问点就是,二维list的排序用python来实现:

1
2
original list: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
sorted list: [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

像之前用的cpp,php甚至是python 2.x,sort方法都可以自己define一个compare function,来进行自定义的排序。但是python3开始把cmp方法给取消了,python3.x对于list的排序是l.sort(key=None, reverse=None)或者sorted(l, key=None, reverse=None),因为有一个key参数的存在,也可以自定义一些排序方法,但是按照这题的需求,对两个不同值是要一个按升序一个按降序的,并不能统一,故很难在一句里面完成。
通过查了官方文档,里面说明,python现在的sort算法是保证稳定(stable)的,也就是说,如果有相同的key存在,他们在排序前后的相对位置是不变的。

Sorts are guaranteed to be stable. That means that when multiple records have the same key, their original order is preserved.

如果有这样的前题,那实现这样一个排序就变得很简单了。直接上代码:

1
2
people.sort(key=lambda x: x[1])
people.sort(key=lambda x: x[0], reverse=True)

可以先按第二个元素排序,再按第一个排序。