首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。