leetcode_406

发表于   |   分类于

Queue Reconstruction by Height

题目戳这

题意

题意是有一个随机站的队列，由n个人组成。给你n个二元的值，每个二元组代表一个人，二元组的元素分别为(h,k)，其中h代表这个人的高度，k代表站在这个人前面并且大于等于这个人身高
的人员个数，让你按照这个二元组重新排列这个队伍。

解法

这个解法不得不说真是精妙了。拿题目中的例子具体说明下就懂了。

[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]，先排序，按照第一个元素从大到小，第二个元素从小到大的规则来进行排序。这个在Python中的写法我不太知道，查了下资料有种方法就是用sorted()先对第二个元素从小到大排列，然后再对第一个元素从大到小排列，写法上跟讲法上刚好是倒着来的，这么写

1
2
3
4
people = sorted(people, key=lambda x:x[1])
#[[7, 0], [5, 0], [7, 1], [6, 1], [5, 2], [4, 4]]
people = sorted(people, key=lambda x:-x[0])
#[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

没毛病。

排好以后我们就可以重新排序了，规则相当的简单明了。就是将二元组一个个的插入新的有序队列，插入的位置就是二元组的第二个元素值。

[7,0] –> [7,0] [7,1] –> [7,0][6,1][7,1] –> [5,0][7,0][6,1][7,1] –> [5,0][7,0][5,2][6,1][7,1] –> [5,0][7,0][5,2][6,1][4,4][7,1]

看，多么的巧妙！刚好利用了这个身高从大到小以及第二个元素从小到大一个个的进行位置插入。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        people = sorted(people, key=lambda x:x[1])
        people = sorted(people, key=lambda x:-x[0])
        
        res = []
        for x in people:
            res.insert(x[1], x)
        
        return res