首页 > 代码库 > Queue Reconstruction by Height

Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example:

Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

一开始我的思路是根据k值从小到大排,如果k值相同则h值从大到小排。然后再遍历排序过后的数组,进行按值插入。看过别人的分析后,更好的方式是先根据h值从大到小排,如果h值相同则k值从小到大排。然后将数组按顺序插入到ArrayList中,经过第二种排序方式的数组,当前即将被插入的数组的k值就是它在list中应有的位置。这是因为数组先按照h值从大到小排序过,因此已经在list中的数组的h值都是大于或者等于当前数组的h值的。代码如下:

技术分享

 

Queue Reconstruction by Height