?LeetCode刷題實戰(zhàn)406：根據(jù)身高重建隊列

示例 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]] 是重新構(gòu)造后的隊列。

示例 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]]

// 版本一
class?Solution?{
public:
????static?bool?cmp(const?vector<int> a, const?vector<int> b)?{
????????if?(a[0] == b[0]) return?a[1] < b[1];
????????return?a[0] > b[0];
????}
????vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
????????sort (people.begin(), people.end(), cmp);
????????vector<vector<int>> que;
????????for?(int?i = 0; i < people.size(); i++) {
????????????int?position = people[i][1];
????????????que.insert(que.begin() + position, people[i]);
????????}
????????return?que;
????}
};

// 版本二
class?Solution?{
public:
????// 身高從大到小排（身高相同k小的站前面）
????static?bool?cmp(const?vector<int> a, const?vector<int> b)?{
????????if?(a[0] == b[0]) return?a[1] < b[1];
????????return?a[0] > b[0];
????}
????vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
????????sort (people.begin(), people.end(), cmp);
????????list<vector<int>> que; // list底層是鏈表實現(xiàn)，插入效率比vector高的多
????????for?(int?i = 0; i < people.size(); i++) {
????????????int?position = people[i][1]; // 插入到下標為position的位置
????????????std::list<vector<int>>::iterator it = que.begin();
????????????while?(position--) { // 尋找在插入位置
????????????????it++; 
????????????}
????????????que.insert(it, people[i]); 
????????}
????????return?vector<vector<int>>(que.begin(), que.end());
????}
};