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