daily_leetcode_2020_1116_406根据身高重建队列

1 题目描述

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

输入:
[[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 题解

将队列按h降序、k升序排序，然后做插入操作：

对于(hi,ki),将它插入下标位ki的位置即可。

这样做的目的就是: 按高低进行排序，高个子在前面，矮个子在后面，对于矮个子(hi,ki)，插到ki位置，就表示前面有ki个比它高的\(这便是题目要求的)

示例：

对于输入 [[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,0], res = [[7,0]]
[7,1], res = [[7,0], [7,1]]
[6,1], res = [[7,0], [6,1], [7,1]]
[5,0], res = [[5,0], [7,0], [6,1], [7,1]]
[5,2], res = [[5,0], [7,0], [5,2], [6,1], [7,1]]
[4,4], res = [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

1. 高个子站好了，矮个子往高个子里面插，矮个子的k影响不到高个子的k

3 代码

class Solution:
    def reconstructQueue(self, people):
        people.sort(key=lambda x: (-x[0], x[1]))
        res = list(list())

        for p in people:
            res.insert(p[1], p)

        return res

    def main(self):
        people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
        print(self.reconstructQueue(people))


if __name__ == '__main__':
    solution = Solution()
    solution.main()