LeetCode 406. Queue Reconstruction by Height 2019-06-28

题目描述

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

注意:
总人数少于1100人。

tag

贪心

样例

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

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

算法1

(贪心) O(n^2)
思路

h是这个人的身高,k是排在这个人前面且身高大于或等于h的人数,所以先按照身高排序,身高一样则按k排序,然后依次安排排序结果中的人。高的人先被安排,因为高的人安排好之后,再去安排矮的人的时候,将矮的人插入高的人之前并不影响排在这个人前面且身高大于或等于h的人数。

复杂度分析:
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
temp = sorted(people, key = lambda x: (-x[0], x[1]))
res = []
for i in temp:
res.insert(i[1], i)
return res

# [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
# 按身高从高到矮排序,一样身高的前面人数小的在前面
# 这样每次插入某个数对时,能够保证当前插入的这个一定小于或者等于前面已插入的数对
# i[1]表示前面有几个人,所以插入在i[1]位置
# [[7,0]] (insert [7,0] at index 0)
# [[7,0],[7,1]] (insert [7,1] at index 1)
# [[7,0],[6,1],[7,1]] (insert [6,1] at index 1)
# [[5,0],[7,0],[6,1],[7,1]] (insert [5,0] at index 0)
# [[5,0],[7,0],[5,2],[6,1],[7,1]] (insert [5,2] at index 2)
# [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] (insert [4,4] at index 4)