根据身高重建队列

根据身高重建队列

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