假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示,其中h是这个人的身高,k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
注意:
总人数少于1100人。
示例
输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
解题思路以及知识点:
- 数组按h降序,若h相同则按k升序的规则对初识数组进行排序。【sort函数排序熟练运用】
- 在排好序的基础之上,将i位置的元素往i前面的任何一个位置移动,都不会对i之前的任何一个位置的k值造成重新计算的影响,仅仅对i元素自身的k值造成影响。
- 根据特点2,关键是将i放入正确位置即可,所谓的正确位置正好是所放位置j===i位置元素的k值。【数组元素调整位置,从后向前插入,熟练使用splice等数组接口】
var reconstructQueue = function(people) {
let len=people.length
//熟练sort接口
people=people.sort(function(a,b){
if(b[0]===a[0]){
return a[1]-b[1]
}else{
return b[0]-a[0]
}
})
for(let i=0;i<len;i++){
for(let j=0;j<=i;j++){
if(j===people[i][1]){
//熟练splice
people.splice(j,0,people.splice(i,1)[0])
break
}
}
}
return people
};