建设工程教育网好还是环球网站好,江苏城乡建设学院网站,wordpress畅言,郑州cms建站模板目录
题目描述
贪心直接插入排序
代码一#xff1a;
代码二#xff1a;
代码三#xff1a; 题目描述
406. Queue Reconstruction by Height 贪心直接插入排序
先按照身高从大到小排序#xff0c;身高相等的人谁的k小谁站前面。
然后按照直接插入排序的想法#xf…目录
题目描述
贪心直接插入排序
代码一
代码二
代码三 题目描述
406. Queue Reconstruction by Height 贪心直接插入排序
先按照身高从大到小排序身高相等的人谁的k小谁站前面。
然后按照直接插入排序的想法将每个人插入到他应该到达的位置。
代码一
复用输入数据people手写直接插入排序
class Solution {
public:vectorvectorint reconstructQueue(vectorvectorint people) {int len people.size();sort(people.begin(),people.end(),[](vectorint p1,vectorint 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){vectorint temp people[i];int pos people[i][1];for(int j i-1;j pos;j--){people[j1] people[j];}people[pos] temp;}}return people;}
};
插入会很耗时时间复杂度是O(lognn^2) 代码二
用vector自己的insert函数位置指定用迭代器。随机迭代器支持n操作
class Solution {
public:vectorvectorint reconstructQueue(vectorvectorint people) {int len people.size();sort(people.begin(),people.end(),[](vectorint p1,vectorint p2){if(p1[0] p2[0])return true;else if(p1[0] p2[0])return p1[1] p2[1];return false;});vectorvectorint 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:vectorvectorint reconstructQueue(vectorvectorint people) {int len people.size();sort(people.begin(),people.end(),[](vectorint p1,vectorint p2){if(p1[0] p2[0])return true;else if(p1[0] p2[0])return p1[1] p2[1];return false;});std::listvectorint 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]);}vectorvectorint res(listres.begin(),listres.end());return res;}
};
