根据身高重建列队
整个插入过程如下：
排序完的people： [[7,0], [7,1], [6,1], [5,0], [5,2]，[4,4]]
插入的过程：
插入[7,0]：[[7,0]]
插入[7,1]：[[7,0],[7,1]]
插入[6,1]：[[7,0],[6,1],[7,1]]
插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
提高速度可以用链表，vector插入慢
class Solution { public: static bool compare(vector<int> a, vector<int> b) { if(a[0] == b[0]) return a[1] < b[1]; else return a[0] > b[0]; } vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { vector<vector<int>> result; sort(people.begin() , people.end(),compare); for(int i=0 ; i < people.size() ;i++) { int pos = people[i][1]; result.insert(result.begin()+pos , 1 , people[i]); } return result; } };
二刷
vector
class Solution { public: static bool cmp(vector<int> &a , vector<int> &b) { if(a[0] == b[0]) return a[1] < b[1]; else return a[0] > b[0]; } vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { vector<vector<int>> result; sort(people.begin(),people.end(),cmp); for(int i=0 ; i<people.size() ;i++) { result.insert(result.begin()+people[i][1] , people[i]); } return result; } };
list
class Solution { public: static bool cmp(vector<int> &a , vector<int> &b) { if(a[0] == b[0]) return a[1] < b[1]; else return a[0] > b[0]; } vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { list<vector<int>> my_list; sort(people.begin(),people.end(),cmp); for(int i=0 ; i<people.size() ;i++) { int point = people[i][1]; auto it = my_list.begin(); while(point--) it++; my_list.insert(it , people[i]); } vector<vector<int>> result(my_list.begin(),my_list.end()); return result; } };
