Leetcode C++《热题Hot 100-48》406.身長に応じてキューを再構築

Leetcode C++《热题Hot 100-48》406.身長に応じてキューを再構築

題

順番を狂わせる一群が行列を作っていると仮定します.各人は整数対(h,k)で表され、hはこの人の身長であり、kはこの人の前に並び、身長がh以上の人数である.このキューを再構築するアルゴリズムを作成します.
注意:総人数は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]]
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/queue-reconstruction-by-height著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.

構想

構想の巧みなテーマ.入力をhから大きいから小さいまで、kは小さいから大きいまで並べ替えます.答えにhを1つずつ挿入し,kの値に従って,新しい挿入のニーズをちょうど満たす.

時間複雑度はソート複雑度,平均nlogn,最悪n二乗

である.

コード

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        vector<pair<int, int>> temp;
        vector<pair<int, int>> res;
        vector<vector<int>> outputRes;
        for (int i = 0; i < people.size(); i++) {
            temp.push_back(make_pair(people[i][0], people[i][1]));
        }
        sort(temp.begin(), temp.end(), cmp);
        for (int i = 0; i < temp.size(); i++) {
            //cout << temp[i].first << " " << temp[i].second << endl;
            res.insert(res.begin()+temp[i].second, temp[i]);
        }
        for (int i = 0; i < res.size(); i++) {
            vector<int> oneres;
            oneres.push_back(res[i].first);
            oneres.push_back(res[i].second);
            outputRes.push_back(oneres);
        }
        return outputRes;

    }

    static bool cmp(pair<int, int> a, pair<int, int> b) {
        if (a.first > b.first)
            return true;
        else if (a.first == b.first && a.second < b.second)
            return true;
        else
            return false;
    }
};