LeetCodeアルゴリズム問題集-406.Queue Reconstruction by Height(高再構築キュー経由)

ランダムなキューがあると仮定すると、各人は1対の数字(h,k)として記述され、hはその人の高さであり、kはその人の前にあり、h以上の人の数である.以上の規則に従ってこのキューを再構築する必要がある.
英語原文:
Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers  (h, k) , where  h  is the height of the person and  k  is the number of people in front of this person who have a height greater than or equal to  h . Write an algorithm to reconstruct the queue.
注: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]]

回答:
最も効率的なバージョン:

struct node{
    pairval;
    int count;
    node*left, *right;
    node(pairn)
    {
        val = n;
        count = 0;
        left = NULL, right = NULL;
    }
};
class Solution {
public:
    vector> reconstructQueue(vector>& people) {
        auto cmp = [](paira, pairb){return a.first==b.first?a.secondb.first;};
        sort(people.begin(), people.end(), cmp);
        vector>ans;
        node* root = NULL;
        for(auto temp:people)
        {
            insert(root, temp.second+1, temp);
        }
        ans = tra(root);
        return ans;
    }
    void insert(node* &root, int n, pairval)
    {
        if(!root)root = new node(val);
        else if(n>(root->count+1))insert(root->right, n - root->count-1, val);
        else root->count++, insert(root->left, n, val);
    }
    vector> tra(node* root)
    {
        vector>ans;
        stacksta;
        while(!sta.empty()||root)
        {
            if(root)
            {
                sta.push(root);
                root = root->left;
            }
            else
            {
                root = sta.top();
                sta.pop();
                ans.push_back(root->val);
                root = root->right;
            }
        }
        return ans;
    }
};

最も簡潔なバージョン:

class Solution {
public:
    vector> reconstructQueue(vector>& people) {
        auto comp = [](const pair& p1, const pair& p2)
                        { return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second); };
        sort(people.begin(), people.end(), comp);
        vector> res;
        for (auto& p : people) 
            res.insert(res.begin() + p.second, p);
        return res;
    }
};