[Leetcode 406] Queue Reconstruction by Height

作者 Shilei Tian 日期 2016-10-19
[Leetcode 406] Queue Reconstruction by Height

题目要求

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]]

解题思路

这道题就是一道排序题,只不过由于它的元素是 pair,因此排序的条件比较奇特。因此,我们需要使用的工具可以定下来了,就是使用 STL 中的 sort 函数,然后定义 comp

那我们如何定义这个 comp 呢?请先考虑,如果给定几张特殊的扑克牌,每张扑克牌上都有两个数字,分别代表题目中的 hk,然后我们需要将这副牌按照题目的要求排列,那么应该如何手动做呢?我想,我应该会先按照 h 对手上的牌进行排序,从大到小。那如果 h 一样怎么办?那么谁的 k 小谁排在前面。这是第一轮排序。假设我的牌是从左向右排列的。然后从最左边一张牌开始,每次拿出来一张,看看它的 k 是多少,就将它插在从左数第 k 个位置,然后再取下一张,重复这个过程,直到所有的牌都重新插好。这是第二轮排序。我们就拿上面它给的例子来看:
Leetcode406

我们通过最初的排序可以得到排序后的结果,然后再对每一张牌进行插入式排序。图中的蓝色箭头就代表我们将这张牌取出来,插到相应的位置。

那么接下来的问题是,我们为什么要按照上面说的规则进行第一轮排序呢?这个问题的回答其实需要参照我们第二轮插入的过程来看。我们在第二轮进行插入的时候,每次都是从最左边(也就是序列的初始位置)开始数第 k 个位置进行插入,这个有些贪心的策略在里面(而 Leetcode 上面也确实将这个题的 Tags 设置为 greedy),就是考虑所谓的局部最合适。因此,为了让后面的元素每次找插入位置的时候从最左边开始且恰好第 k 个位置之前的元素都要大于它,这需要我们在每次选择元素的时候按照 h 递减的次序选,因此才有了第一轮排序中的h 进行排序,大的放在前面这个策略了。我们第一轮排序中还有一个原则是,如果 h 一样,那么谁的 k 小谁排在前面。这个是为什么呢?举个反例就可以说明了。还看第二轮,假如 k 大的排在前面,那么我们首先会拿到大的那张牌C1,假设它的 k 值是 k1,然后将它插在第 k1 个位置,接下来我们会拿到小的那张牌C2,假设它的 k 值是 k2,且 k1 > k2,那么按照我们第二轮的插入策略,必然将它插在 C1 的前面,这个时候虽然 C2k 值是对着的,但是 C1 的值就不应该是 k1,而应该是 k1 + 1 了,就不对了。

代码

有了上述手动排序的过程,我们就不难写出相应的 C++ 代码了,这里我们用了一些 C++11 新特性,比如 Lambda 表达式、auto 符号等。

class Solution {
public:
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
sort(people.begin(), people.end(), [](const pair<int, int> &a, const pair<int, int> &b){
return a.first > b.first || (a.first == b.first && a.second < b.second);
});
vector<pair<int, int>> ret;
for (auto p : people) {
ret.insert(ret.begin() + p.second, p);
}
return ret;
}
};