leetcode.com上随机选择到这个题目,讲道理,第一遍没看懂题目啥意思,有很多人也在吐槽题目读不懂I don't understand the question. Reconstruct the queue to what?直到我打开讨论区看了一眼别人的python代码,如果你也看不懂这个题目描述,我结合中文版的描述加以完善:
现在有一个队列,每个人由一个整数对(h, k)表示,其中h是这个人的身高,k是排在这个人前面且身高大于或等于h的人数。但现在输入的序列是随机打乱的,编写一个算法来重建这个队列。
输入队列:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
这里输入队列第二项是不符合要求的,身高比4高的前面目前只有7一个人。

输出队列:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
将输入序列调整后的队列符合要求,第一个身高5的,前面没有比他高的,身高7也是同样的道理,依次类推可以验证输出队列符合要求。
代码实现中用到了lambda表达式 vector的插入。

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),[](const vector<int> &a,const vector<int> &b){
           return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
        });    
        
        vector <vector<int>> res;
        
        for(auto person :people)
        {
            res.insert(res.begin() + person[1],person);
        }
        
        return res;    
    }
};

上面代码的解题思路是:

    输入序列:
    // [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
    //  
    第一步先排序按照身高
    //
    // [7, 0] 0
    // [7, 1] 1
    // [6, 1] 2
    // [5, 0] 3
    // [5, 2] 4
    // [4, 4] 5
    第二步按照前面有多少个人插入
    //  
    // [7, 0]
    // [7, 0] [7, 1] 
    // [7, 0] [6, 1] [7, 1]
    // [5, 0] [7, 0] [6, 1] [7, 1]
    // [5, 0] [7, 0] 5, 2] [6, 1] [7, 1]
    // [5, 0] [7, 0] 5, 2] [6, 1] [4, 4] [7, 1]

for循环中的代码我在leetcode上看有的人还判断begin() + person[1]是否超过当前元素个数,其实这里是完全没有必要的,为什么呢?可以参考上面的演示流程中,第二步插入的时候先插入了[7,0],因为我们前面有排序,所以7这里是最大的,接着插入[7,1]在末尾,此时已经有两个元素,接着插入了[6,1],因此不会出现那种越界的情况(segment fault).
其实上面的解释不够一针见血,概括起来就是一句话,我们第一步按照身高,身高相同按照前面人数少排序,因此,插入的时候不会出现当前元素个数小于要插入的位置的情况。
例子如下:

// Program below illustrates the
// vector::insert() function

#include <bits/stdc++.h>
using namespace std;

int main()
{
    // initialising the vector
    vector<int> vec = {10};

    // inserts 20 at begin + 1
    auto it = vec.insert(vec.begin() + 1, 20);

    // inserts 30 at begin + 3 ,will segmentfault
    vec.insert(vec.begin() + 3, 30);

    cout << "The vector elements are: ";
    for (auto it = vec.begin(); it != vec.end(); ++it)
        cout << *it << " ";

    return 0;
}

我们在vec.beigin() + 3位置插入元素30,此时会segmentfault,因为此时只有2个元素,最多允许在末尾插入,如果将vec.begin() + 3修改为vec.begin() + 2则执行成功,输出结果10 20 30.