首页 > 代码库 > sort学习 - LeetCode #406 Queue Reconstruction by Height

sort学习 - LeetCode #406 Queue Reconstruction by Height

用python实现多级排序,可以像C语言那样写个my_cmp,然后在sort的时候赋给参数cmp即可

但实际上,python处理cmp 是很慢的,因为每次比较都会调用my_cmp;而使用key和reverse就快得多,因为只需要在排序开始时处理一次即可,因此在排序的时候能不用cmp就尽量不用

另外可以用operator函数中的itemgetter,和attrgetter实现基于key的(多级)排序:

from operator import itemgetter, attrgetter
sorted(people, key=itemgetter(0,1))
sorted(people, key=attrgetter(h,k))

itemgetter通过属性的下标指定key,attrgetter通过属性名指定key

 

趁热打铁,用sort实现一下 LeetCode #406 Queue Reconstruction by Height

https://leetcode.com/problems/queue-reconstruction-by-height/

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

 

基本思路很简单,对people进行排序,h越大k越小的排越前,然后按顺序先给个子高的排位置,再给个子矮的排

因为个子高的位置排好后,再怎么对个子矮的排,都不会影响个子高的人的相对位置

这里的排序涉及两个key,所以要用多级排序

 

先用传统的cmp方法实现

def reconstructQueue(self, people):
  def my_cmp(p1,p2):
        return cmp(p2[1],p1[1]) if p1[0]==p2[0] else cmp(p1[0],p2[0])
    
    people.sort(cmp = my_cmp,reverse = True)
    ans = []
    for peo in people:
        ans.insert(peo[1],peo)
    return ans

耗时情况

技术分享

 

现在改用基于key实现多级排序,由于h是降序,k是升序,所以暂时还不知道怎么用itemgetter实现,只会自己写一个my_key =  =、

由于sort不reverse,所以my_key中返回的是负的h(people[0])和正的k(people[1])来分别实现降序和升序

def reconstructQueue(self, people):
    def my_key(people):
        return -people[0],people[1]
    
    people.sort(key=my_key)
    ans = []
    for peo in people:
        ans.insert(peo[1],peo)
    return ans

耗时情况

技术分享

可以看出sort基于key时在速度上确实快于基于cmp

sort学习 - LeetCode #406 Queue Reconstruction by Height