406.|406. Queue Reconstruction by Height 406.QueueReconstructionbyHeight

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.
Note:
The number of people is less than 1,100.
Example

Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

思路:算法是别人想的,太屌了学不来.
先将vector排序,按h排序(降序),h值相等按k值排(升序),得到:

7 0 7 1 6 1 5 0 5 2 4 4

然后从头开始将vector中元素(h,k)插入新vector的第k个位置:
第一次:[7,0]
第二次:[7,0],[7,1]
第三次:[7,0],[6,1],[7,1]
第四次:[5,0],[7,0],[6,1],[7,1]
第五次:[5,0],[7,0],[5,2],[6,1],[7,1]
第六次:[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]
算法的简单解释就是:排序处理后,h值大的放前面,因为越大的数限制越小; 而越小的数由于要保证前面有k个比他大的数,限制越多.
对于h值相等的数,就看k值,因为小的数不会影响大数的k,所以先放大数之后,小数就可以直接放到vector的第k个位置,而不会影响别人.
这里用到sort的三参数版本,最后一个参数为比较函数
http://zh.cppreference.com/w/cpp/algorithm/sort

template< class RandomIt, class Compare > void sort( RandomIt first, RandomIt last, Compare comp ); first, last - 要排序的元素范围comp - 比较函数对象（即满足比较 (Compare) 概念的对象），若第一参数小于（即先序于）第二参数则返回 ?true 。比较函数的签名应等价于如下者： bool cmp(const Type1 &a, const Type2 &b); 签名不必拥有 const & ，但函数对象必须不修改传递给它的对象。类型 Type1 与 Type2 必须使得 RandomIt 类型的对象能在解引用后隐式转换到这两个类型。 ?

代码:

vector> reconstructQueue(vector>& people) { //先对people做排序处理,其中比较函数使用lambda表达式 sort(people.begin(), people.end(), [](const pair p1, const pair p2) { return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second); }); vector【406.|406. Queue Reconstruction by Height】> res; for (auto p : people) {//从头遍历people,将p按k值插入res res.insert(res.begin()+p.second, p); } return res; }