跳转至

LeetCode: 406. 根据身高重建队列

1、题目描述

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示,其中h是这个人的身高,k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意: 总人数少于1100人。

示例

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

2、解题思路

​ 首先来分析一下,按照位置来划分

  • 首先,建立结果集
  • 然后第0号位置,可能出现哪些元素?肯定是从身高等于0的里面选,如果有多个呢,那么取出最小的那个即可
  • 如上面,也就是[5,0]
  • 然后是第1个位置,可能出现哪些元素呢?就是刚刚0号位置剩下的元素,加上前面人数为1的那些元素,从这里面找出最小的那个值

​ 于是,根据上面的思路,我们发现,假设我们已经按照身高从大到小排好序,并且,身高相同的,使用人数从小到大排序,然后使用插入法,会发生什么呢?

​ 首先,最大的那个元素,会被放到第一个,然后从第二个元素开始,按照人数进行插入,如果是身高相同的话,会按照人数依次排列,这正是我们想要的结果

​ 也就是说,首先,第一次排序,已经将所有的身高相同的放入了正确的顺序

​ 然后,我们将身高低于这个的,依次插入对应的位置,这样每一个元素,大于这个元素的个数也是正确的

​ 所以,主要需要理解的点,就在于下面:

  • 首先将身高相同的顺序确定下来
  • 然后,因为身高是按照从大到小排序的,因此,直接按照对应的人数进行插入,就得到正确的大于等于的人数

举个例子:

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
首先我们按照身高从大到小排序,然后身高相同,按照人数排序
[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
我们看到,身高相同的,例如7,5,最终顺序目前已经是正确的了
res = []
首先将[7,0]按照人数插入结果集
res = [[7,0]]
然后是[7,1]
res = [[7,0],[7,1]]
再来是[6,1]
res = [[7,0],[6,1],[7,1]]
现在就能看出来了,[6,1]插入的位置,因为是按照降序排列的,因此,直接插入1这个位置,保证前面有1个大于等于当前数字的,问题的精髓就在这里了。
import functools
class Solution:
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        sort_key = functools.cmp_to_key(lambda x, y: y[0] - x[0] if x[0] != y[0] else x[1] - y[1])
        sort_people = sorted(people, key=sort_key)
        res = []

        for i in sort_people:
            res.insert(i[1], i)

        return res

​ 在python3里面,排序函数不支持比较函数了,可以使用functools里面提供的,将函数转换成key