leetcode 406. 根据身高重建队列

2023.8.2

        这题一开始有点让人懵逼的是有两个维度，一个是身高，还一个是前面人高于自己的人数。这种题一般需要先固定一个维度，再去确定另外一个维度，不要想着兼顾。

        经过纸上模拟，我的思路是先通过身高进行从大到小排序，如果身高相同则k值小的站前面。排完序之后再将第二个维度 k 值 当作索引重建新的二维数组。代码细节如下：

class Solution {
public:static bool cmp(vector<int>& a , 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>> ans;for(int i=0; i<people.size(); i++){ans.insert(ans.begin()+people[i][1],people[i]);}return ans;}
};

---

 优化：

        考虑到vector的插入效率比较低下，可以使用链表list来进行插入，时间效率会高很多：

class Solution {
public:static bool cmp(vector<int>& a , 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>> ans;for(int i=0; i<people.size(); i++){int index = people[i][1];auto it = ans.begin();while(index--){it++;}ans.insert(it,people[i]);}return vector<vector<int>>(ans.begin(),ans.end()); }
};