2023.8.2

? ? ? ? 這題一開始有點讓人懵逼的是有兩個維度，一個是身高，還一個是前面人高于自己的人數(shù)。這種題一般需要先固定一個維度，再去確定另外一個維度，不要想著兼顧。

? ? ? ? 經(jīng)過紙上模擬，我的思路是先通過身高進行從大到小排序，如果身高相同則k值小的站前面。排完序之后再將第二個維度 k 值 當(dāng)作索引重建新的二維數(shù)組。代碼細(xì)節(jié)如下：

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;}
};

?優(yōu)化：

? ? ? ? 考慮到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()); }
};