根据身高重建队列

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

题解

/**
 * @param {number[][]} people
 * @return {number[][]}
 */
var reconstructQueue = function(people) {
    // people.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
    people.sort((a, b) => a[0] - b[0]);
    const n = people.length;
    let target = [];
    people.forEach((v) => {
        let spaces = v[1] + 1;
        for(let i=0;i<n;++i){
            if(target[i] === void 0 || target[i][0] === v[0]){
                spaces--;
                if(spaces <= 0 && target[i] === void 0){
                    target[i] = v;
                    break;
                }
            }
        }
    })
    return target;
};

思路

当每个人的身高都不相同时,我们将他们按照身高从小到大进行排序,之后使用插入的方式进行还原,首先我们假设有n个人,然年后我们将要插入第i个人,现在第0 ... i-1已经排好了位置,无论他们如何站队,对我们将要插入的第i个人都没有影响,对于第i ... n-1个人,只要插入的位置在第i个人前,就能够对第i个人产生影响,之后我们就可以建立一个长度为n的数组,对排序过后的数组将其分别插入,那么当我们插入第i个人时,其要插入的位置必定是其高度大于它的数量+1,例如我们第一个要插入的是(5, 2),那么他的位置就是<empty>, <empty>, (5, 2),也就是说给他安排的空位是第三个位置,此外由于其是队列的第一个数值,其后的值必定比他大,所以其后的值按照同样的规则进行插入是可以满足条件的,在这里需要特殊处理一下身高相同的人,如果身高相同,同样应该将其作为一个空位去处理,之后特殊处理这个位置如果是空位则直接插入,否则插入到其后边的位置。在官方给出的题解是在排序的时候根据身高升序,在根据前边身高高于他的人的数量进行降序,之后就可以直接进行上述规则而不用特殊处理相等的情况,举个例子,当我们根据上述的排序规则进行排序后得到(5, 2) (5, 0) ...,那么先插入(5, 2),再插入(5, 0)可以得到(5, 0), <empty>, (5, 2),当然我们经过特殊处理相同的情况也是可以得到的,但是如果不经过特殊处理则会得到(5, 0), <empty>, <empty>, (5, 2)显然是不合适的。首先进行排序,这里只是按照身高进行排序,之后取得数组长度n,定义目标数组,遍历排序过后的数组,定义好应该取得的空位置并+1,之后进行n次循环,如果这个位置未定义或者值与要插入的值相同,那么就将应该减少的空位置数量-1,如果应该置入的空位置数量小于0并且这个位置是空,那么就将该值插入该位置并结束内层循环,最后返回目标数组即可。

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

https://leetcode-cn.com/problems/queue-reconstruction-by-height/