[数据结构与算法]leetcode 406. 根据身高重建队列 详细注解

题目链接

算法一

贪心+树状数组+二分

时间复杂度O（nlog^2(n)）

思路

先放身高最小的，然后剩余的都是身高比它大的，之前放的身高更小的不需要在考虑了，如果相等放位次高的，这样位次低的不受影响，这里用树状数组统计有几个空余位置即没放的位置，这些位置将要放的人身高一定比当前身高高，所以对应位次就是前边有几个空白位置。

C++ 代码

class Solution {
public:
    int n;
    vector<int>tr;
    int lowbit(int x)
    {
        return x&-x;
    }
    void add(int x,int v)
    {
        for(int i=x;i<=n;i+=lowbit(i))tr[i]+=v;
    }
    int query(int x)
    {
        int res=0;
        for(int i=x;i;i-=lowbit(i))res+=tr[i];
        return res;
    }
    //对于身高从小往大排，对于位次从大往小排
    static bool cmp(vector<int> a,vector<int> b)
    {
        if(a[0]!=b[0])return a[0]<b[0];
        else return a[1]>b[1];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        n=people.size();
        tr.resize(n+1);
        vector<vector<int>>res(n);
        sort(people.begin(),people.end(),cmp);
        
        for(auto p:people)
        {
            int l=1,r=n;
            while(l<r)
            {
                int mid=(l+r)/2;
                if(mid-query(mid)>=p[1]+1)r=mid;
                else l=mid+1;
            }
            res[r-1]=p;
            add(r,1);
        }
        return res;
    }
};

算法二

贪心O

复杂度O（n^2）

思路

先放身高高的，这样身高低的不会对其有所影响，如果相等放位次低的，位次即所在位置，然后类似于滑动窗口，对每个人往里边插到合适位置即可

class Solution {
public:
    static bool cmp(vector<int>a,vector<int>b)
    {
        if(a[0]!=b[0])return a[0]>b[0];
        return a[1]<b[1];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    int n=people.size();
    sort(people.begin(), people.end(), cmp);
    vector<vector<int>> res;
    for(auto p:people) res.insert(res.begin()+p[1],p);
    return res;
    }
};