Share some knowledge, post study notes or talk nonsense.

0%

[LeetCode 406] Queue Reconstrucion By Height (根据高度重建队列)

Description:

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.

Strategy:

  • 先按照身高h从高到低对(h, k)排序,如果h相同,k小的排在前面
  • 新建一个空的res数组,遍历排好序后的(h, k)对,依次插入到res数组索引为k的位置即可

这里有两个key point:1. 身高高的先插入;2. 每次插入的位置(索引)就是k。这样为什么可以保证是对的呢?

我们可以假设第i-1次插入后queue是正确的,考虑第i次插入的情形:由于是身高高的优先插入,因此当前res数组里的所有人(h0,k0),...,(hi1,ki1)(h_0, k_0), ..., (h_{i-1}, k_{i-1})的身高都比即将要插入的(hi,ki)(h_i, k_i)要高,所以在位置kik_i插入对于(hi,ki)(h_i, k_i)来说一定是正确,并且对于那些已经在res数组中的元素来说,新插入一个身高比他们都小的人并不会影响他们的排列。其实这就是贪心,局部最优推出全局最优,这道题则是局部正确推出全局正确。(然而我一开始并没有想出来orz)

Implementation:

至于实现就比较简单了

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// https://github.com/grandyang/leetcode/issues/406
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), [](vector<int>& a, vector<int>& b) {
return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
});
vector<vector<int>> res;
for (auto a : people) {
res.insert(res.begin() + a[1], a); // vector的insert时间复杂度是O(n)
}
return res;
}
};

Solution 2

没有使用额外的空间,但多了erase的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// https://github.com/grandyang/leetcode/issues/406
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), [](vector<int>& a, vector<int>& b) {
return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
});
for (int i = 0; i < people.size(); i++) {
auto p = people[i];
if (p[1] != i) {
people.erase(people.begin() + i);
people.insert(people.begin() + p[1], p);
}
}
return people;
}
};

C++ Grammar

1
2
3
4
// 使用了lambda表达式,创建了一个匿名的函数对象
sort(people.begin(), people.end(), [](vector<int>& a, vector<int>& b) {
return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
});