1.题目基本信息
1.1.题目描述
假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [h_i, k_i] 表示第 i 个人的身高为 h_i ,前面 正好 有 k_i 个身高大于或等于 h_i 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ,其中 queue[j] = [h_j, k_j] 是队列中第 j 个人的属性(queue[0] 是排在队列前面的人)。
题目意思: 原本有个排列正确的队列,现在被打乱成了people,现在需要我们根据打乱的people数列恢复之前正确的队列
1.2.题目地址
https://leetcode.cn/problems/queue-reconstruction-by-height/description/
2.解题方法
2.1.解题思路
本题只看官方题目,比较不太好理解。但是通过案例理解就很好理解。本质就是:原本有个排列正确的队列,现在被打乱成了people,现在需要我们根据打乱的people数列恢复之前正确的队列。 理解题意后,直接排序、遍历就很容易了
2.2.解题步骤
第一步,将people按身高升序、高于人数降序进行排列
第二步,初始化返回数组。并遍历people,每遍历一次的结果是在result中填上一个空位。对于遍历的第一个person,其余的length-1的人身高均大于或等于其,所以只需填到peroson[1]+1个空位处即可;对于后面person,第person[1]+1个空位也是合法位置(注意:对于当前遍历的person,前面的部分坑已经被前面遍历的填了)。最后,对于一种特殊情况的解释,就是相同身高但是person[1]不同的人,这种通过person[1]多的人先遍历,避免了对person[1]少的人的填坑的影响。
3.解题代码
Python代码
# 题目意思: 原本有个排列正确的队列,现在被乱成了people,现在需要我们根据打乱的people数列恢复之前正确的队列
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
length=len(people)
# 第一步,将people按身高升序、高于人数降序进行排列
people.sort(key=lambda person:[person[0],-person[1]])
# 第二步,初始化返回数组。并遍历people,每遍历一次的结果是在result中填上一个空位。对于遍历的第一个person,其余的length-1的人身高均大于或等于其,所以只需填到peroson[1]+1个空位处即可;对于后面person,第person[1]+1个空位也是合法位置(注意:对于当前遍历的person,前面的部分坑已经被前面遍历的填了)。最后,对于一种特殊情况的解释,就是相同身高但是person[1]不同的人,这种通过person[1]多的人先遍历,避免了对person[1]少的人的填坑的影响。
result=[[] for _ in range(length)]
for person in people:
blankPosCnt=person[1]+1
for i in range(length):
if not result[i]:
blankPosCnt-=1
if blankPosCnt==0:
result[i]=person
break
return result
C++代码
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
int length=people.size();
sort(people.begin(),people.end(),[](const vector<int>& u,const vector<int>& v){
return u[0]<v[0] || (u[0]==v[0] && u[1]>v[1]);
});
vector<vector<int>> result(length);
for(auto person:people){
int blankPosCnt=person[1]+1;
for(int i=0;i<length;++i){
if(result[i].empty()){
blankPosCnt--;
if(blankPosCnt==0){
result[i]=person;
break;
}
}
}
}
return result;
}
};