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.
The number of people is less than 1,100.
示例
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]]
限制条件
没有明确给出.
解题思路
我的思路：
看到这道题，我的第一个反应就是应该要排一下序，由于是包含两个数字，所以第一个数字相同的时候，按照第二个数字的逆序排列（为什么要这样做，我也不知道，做的时候觉得应该是这样。。。）。比如数组people：
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
排序后：
[[4,4], [5,2], [5,0], [6,1], [7,1], [7,0]]
然后我先挑出最小的第二个数字为0的元素，放入到另外的一个数组result里，并将其从people中删除。
然后从people最后一个元素开始，将元素放入到另外的一个数组result里。
设置一个变量ge，用于统计大于等于people元素的个数。每次都从result的第一位开始，比较result中每一元素与当前people元素的第一个数字，大于或等于时更新ge，如果ge等于people元素的第二个数字，则就把该people的元素插入到result元素的后面，并重置ge为0，继续下一个people元素。过程如下：
1.
people: [7,0]
result: [[5,0]]
ge: 一开始就是0，在[5,0]后面插入[7,0]
2.
people: [7,1]
result: [[5,0], [7,0]]
ge: 经过[7,0]后，ge=1
所以在[7,0]后面插入[7,1]
3.
people: [6,1]
result: [[5,0], [7,0], [7,1]]
ge: 经过[7,0]后，ge=1
所以在[7,0]后面插入[6,1]
4.
people: [5,2]
result: [[5,0], [7,0], [6,1], [7,1]]
ge: 经过[5,0]和[7,0]后ge=2
所以[7,0]之后插入[5,2]
5.
people: [4,4]
result: [[5,0], [7,0], [5,2], [6,1], [7,1]]
ge: 经过[5,0],[7,0],[5,2]和[6,1]后ge=4
所以[6,1]之后插入[4,4]
结果就是[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
最后是Accept了，然后去看discuss时，我惊呆了，大牛们的解法太优雅了。下面给出他们的解法。
参考思路：
同样，他们的第一步也是排序，排序的规则跟我自己想的是反过来了，即
people：
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
排序后：
[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
然后从数组people第一个元素开始，放入到数组result中，放入的位置就是离result开始位置偏移了元素第二个数字后的位置。如下：
1.
people: [7,0]
插入到离开始位置偏移了0个距离的位置。
result: [[7,0]]
2.
people: [7,1]
插入到离开始位置偏移了1个距离的位置，即插入到[7,0]的后面。
result: [[7,0], [7,1]]
3.
people: [6,1]
插入到离开始位置偏移了1个距离的位置，即插入到[7,0]的后面。
result: [[7,0], [6,1], [7,1]]
4.
people: [5,0]
插入到离开始位置偏移了0个距离的位置，即插入到[7,0]的前面。
result: [[5,0], [7,0], [6,1], [7,1]]
5.
people: [5,2]
插入到离开始位置偏移了2个距离的位置，即插入到[7,0]的后面。
result: [[5,0], [7,0], [5,2], [6,1], [7,1]]
5.
people: [4,4]
插入到离开始位置偏移了4个距离的位置，即插入到[6,1]的后面。
result: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
这种算法体现了元素第二个数字与其插入位置的关系，所以通过简单的一个for循环就可以搞定。
代码
我的代码
class Solution {
public:
static bool myCompare(const pair<int, int> &a, const pair<int, int> &b) {
if (a.first == b.first)
return a.second > b.second;
else
return a.first < b.first;
}
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
vector<pair<int, int>> result;
vector<pair<int, int>>::iterator itr;
if (people.empty())
return people;
sort(people.begin(), people.end(), myCompare);
itr = people.begin();
while (itr != people.end()) {
if (itr->second == 0)
break;
itr++;
}
result.push_back(*itr);
people.erase(itr);
for (int i = people.size() - 1; i >= 0; i--) {
int ge = 0;
itr = result.begin();
for (; itr != result.end(); itr++) {
if (itr->first >= people[i].first)
ge++;
if (ge == people[i].second) {
result.insert(itr + 1, people[i]);
break;
}
}
}
return result;
}
};
参考代码
class Solution {
public:
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
vector<pair<int, int>> result;
// use lambda expression as the third parameter
sort(people.begin(), people.end(), [](pair<int, int> a, pair<int, int> b){
return a.first > b.first || (a.first == b.first && a.second < b.second);
});
for (auto p: people) {
result.insert(result.begin() + p.second, p);
}
return result;
}
};
总结
虽然今天靠自己的努力先做出来，但是对比了大牛们的解法，我真是惊叹他们的优雅，同时为自己简陋的代码而羞愧，他们不仅思路上压制，实现上还用了lambda表达式，for范围循环，真是看着赏心悦目，我要好好地向他们学习，平时要多注意自己的实现方式，多去修改自己的代码。
今天真的学到了很多东西，不仅是解题思路上的，还有代码风格上的体悟，明天继续填坑，努力加油！
