当前位置：首页 > java >正文

406. Queue Reconstruction by Height

java 2025/6/18 19:55:50

题目描述

贪心+直接插入排序

代码一：

代码二：

代码三：

题目描述

406. Queue Reconstruction by Height

贪心+直接插入排序

先按照身高从大到小排序，身高相等的人谁的k小谁站前面。

然后按照直接插入排序的想法，将每个人插入到他应该到达的位置。

代码一：

复用输入数据people，手写直接插入排序

class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {int len = people.size();sort(people.begin(),people.end(),[](vector<int> &p1,vector<int> &p2){if(p1[0] > p2[0])return true;else if(p1[0] == p2[0])return p1[1] < p2[1];return false;});for(int i = 0;i <len;i++){if(people[i][1] < i){vector<int> temp = people[i];int pos = people[i][1];for(int j = i-1;j >= pos;j--){people[j+1] = people[j];}people[pos] = temp;}}return people;}
};

插入会很耗时，时间复杂度是O(logn+n^2)

代码二：

用vector自己的insert函数，位置指定用迭代器。随机迭代器支持+n操作

class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {int len = people.size();sort(people.begin(),people.end(),[](vector<int> &p1,vector<int> &p2){if(p1[0] > p2[0])return true;else if(p1[0] == p2[0])return p1[1] < p2[1];return false;});vector<vector<int>> res;res.reserve(len);for(int i = 0;i <len;i++){int pos = people[i][1];if(pos < i){res.insert(res.begin()+pos,people[i]);}else{res.push_back(people[i]);}}return res;}
};

代码三：

用链表来插入。不过寻找插入位置仍然是O(n)的时间复杂度，因为在 C++ 中，std::list 的迭代器是双向迭代器，不支持随机访问（即不能直接使用 + 运算符进行偏移）

class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {int len = people.size();sort(people.begin(),people.end(),[](vector<int> &p1,vector<int> &p2){if(p1[0] > p2[0])return true;else if(p1[0] == p2[0])return p1[1] < p2[1];return false;});std::list<vector<int>> listres;for(int i = 0;i <len;i++){if(people[i][1] < i){int pos = people[i][1];listres.insert(std::next(listres.begin(),pos),people[i]);}elselistres.push_back(people[i]);}vector<vector<int>> res(listres.begin(),listres.end());return res;}
};