LeetCode 406. Queue Reconstruction by Height

题解

这题可以巧妙地被结构为一道插排问题。
先sort,h从大到小排,h相同按k数从小到大。
此时数列前方的大的数已经成为一个局部完整序列了。因为小h不会影响
大h的k正确性,然后慢慢考虑后面的h要插入哪里就可以了。
这不就是插入排序么。


Code
class Solution {
public:
    static bool cmp(pairint, int a, pairint, int b){
        return a.first == b.first ? a.second  b.second : a.first  b.first;
    }
    vectorpairint, int reconstructQueue(vectorpairint, int people) {
        sort(people.begin(),people.end(),cmp);
        
        int n=people.size();
        vectorpairint, int res(n);
        for(int i=0;in;i++){
                
            for(int j= i;jpeople[i].second;j--){ // 调位置 向后移动
                swap(res[j],res[j-1]);
            }
            res[people[i].second]= {people[i].first,people[i].second};// 插入空缺
        }
        return res;
    }
};
最新回复(0)
/jishu_2Fmv9vGHpoO7RQscc5zONhx6emY9UlSXAVdtGweb1Kjg_3D4858371
8 简首页