题目描述
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.
Example1:
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，让其排序
- 排序后的 [5, 0] //表示身高为5的，前面没有比他高的
- [7, 0] // 身高为7的，也没有比他高的 -> 前面的5比他矮
- [5, 2] // 身高为5的，前面超过或者等于的 有2个 即[5, 0],[7,0]
- 思路理解清楚了之后，需要想解决办法
- 可以先排序，先按身高进行排序，如果相等，再按第二个关键字 从小到大进行排序
- 比如这个排序后的结果为 [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
- 然后我们将不符合规定的插入到指定位置即可 比如 现在 [7, 0][7, 1] 不用动，[6, 1] 表示前面超过的有1个，即我们插入到 [7,0][7,1]之间即可，变成 [7,0][6,1][7,1]这样就符合最后的结果了。
- vector insert(pos, data) // 在pos中插入data数值
class Solution {
public:
static bool cmp(vector<int>& a, vector<int>& b){
return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), cmp);
vector<vector<int>> res;
for(auto p : people){
res.insert(res.begin() + p[1] ,p); // pos, array 第一个参数为插入的位置，第二个为具体的数值
}
return res;
}
};
