📏406.根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

将给定的二维数组重新排列,使其符合 [hi, ki]的要求

示例

示例 1：

• 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
• 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
• 解释：
  • 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
  • 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
  • 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
  • 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
  • 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
  • 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
  • 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

• 输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
• 输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

• 1 <= people.length <= 2000
• 0 <= hi <= 10^6
• 0 <= ki < people.length

题目数据确保队列可以被重建

思路

基本思想

第i个人的属性ki是几,这个人在queue中的位置最小就是ki,也就是说这个人前面得至少有ki个人才有机会出现i前面有ki个比他高的

例如一个people数组为[[2,1],[1,1]]就不一个合法,people2的位置最少应该从1开始,但是现在从0开始

对people先按照身高进行降序排列,身高相同的按照ki升序排序,这样可以保证第i个人之前的身高全部都是大于等于自己的

之后再按照ki将[hi, ki]插入queue中的ki即可,这样就可以保证每个人前面都有ki个比他高的，因为插入时从前到后拿元素，后拿到的元素小，如果后拿到的元素与已插入的元素对应的ki相等，插入ki位置之后，先来的元素会被挤到后面，此时排在旧元素前面的元素比自身小，ki的性质还是保留，所以可以这样插入

就是一个排序的逻辑，先按身高降序，身高相同按ki升序，之后按照ki插入对应的位置即可

执行流程

1. 排序:先按身高降序,身高相同再按ki升序
2. 插入元素:每个人将ki当成自己在queue中的下标进行插入

这样再插入时即使有两个元素[7,0],[5,0]都要插入0号位置,但是[7,0]排序之后在[5,0]的前面会先插入,[5,0]插入之后会将[7,0]挤到后面,也符合要求

并且由于排序后第i个人之前全是不矮于自身的人,所以向前挪动到ki位子,变成前面有ki个人不矮于自己

代码

根据以上分析,得出以下代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    //自定义排序函数
    static bool com(const vector<int> v1,const vector<int> v2){
        //身高相同ki大的在后面
        if(v1[0]==v2[0])    
            return v1[1]<v2[1];
        //身高高的在前面
        return v1[0]>v2[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),com);
        list<vector<int>> vec_temp;
        //排序完成之后就开始插入   
        for(auto elem : people){
            //插入到ki位置,可能会被向后挤
            int pos=elem[1];
            auto it=vec_temp.begin();
            //找到插入位置
            while(pos>0){
                --pos;
                ++it;
            }
            //插入
            vec_temp.insert(it,elem);
        }
        //插入完成之后，将list转化成vector,返回一个匿名对象
        return vector<vector<int>>(vec_temp.begin(),vec_temp.end());
    }
};

总结

题目要求第i个人之前至少有ki个人不矮于自己,所以先进行身高的降序,让不矮于自己的全在自己前面,在进行ki的升序,形成[7,0],[7,1]的情况\

这里的不矮于自己的先全在自己前面就是一个贪心

然后不矮于自己的太多了,只要ki个,就把vector移动到ki上即可

之后再进行插入,由于已经有序,大的会先插入,小的插入时会将大的挤到后面,形成有ki个不矮于自己的局面,大的本来插入到ki位置上,但是被后来的小元素挤到后面也不影响,因为前面多出的元素是小元素

并且由于插入比较频繁,所以使用list,最后将链表转换成vector