美文网首页
406. 根据身高重建队列

406. 根据身高重建队列

作者: 彼小星星空下看星星 | 来源:发表于2020-11-16 19:55 被阅读0次

    假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(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]]

    解题思路以及知识点:

    1. 数组按h降序,若h相同则按k升序的规则对初识数组进行排序。【sort函数排序熟练运用】
    2. 在排好序的基础之上,将i位置的元素往i前面的任何一个位置移动,都不会对i之前的任何一个位置的k值造成重新计算的影响,仅仅对i元素自身的k值造成影响。
    3. 根据特点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
    };
    
    

    相关文章

      网友评论

          本文标题:406. 根据身高重建队列

          本文链接:https://www.haomeiwen.com/subject/oivzbktx.html