LeetCode 筆記 - 406. Queue Reconstruction by Height

Posted on

題目在此 406. Queue Reconstruction by Height

給定一群人的身高與條件，people[i] = [hi, ki]
h 是身高，k 是前面必須有 k 個跟他一樣高或比他高的人

請給出符合條件的順序

解題思維

這題的 hint 說從最矮的開始思考，但筆者覺得從高的思考比較順

首先先把題目排序，高的在前面，一樣高的就需要比較少人在前面的人排前面
因此排序的式子可以寫成這樣

1
people.sort(key=lambda x : (-x[0], x[1]))

此時就可以按照 k 把每個人放進答案序列的第 k 個位子
因為從最高的開始放，所以之後就算有其他人放到較高的人前面，也不會影響條件

我們來用 Exmaple 1 來演示一下

1
2
3
4
5
6
7
8
9
# after sorting 
people = [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

[[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

程式碼

1
2
3
4
5
6
7
8
9
10
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:

        result = []
        people.sort(key=lambda x : (-x[0], x[1]))
        
        for p in people:
            result.insert(p[1], p)

        return result

也許你也會想看看