406.根据身高重建队列(Medium)
# 题目描述
假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = (h, k) 两个数,第一个h代表身高,第二个k代表高于或等于自己的人数
请你重新构造并返回输入数组 people 所表示的队列。
# 样例
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]]
解释:
编号为 0 的人身高为 5 ,没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ,没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ,有 2 个身高更高或者相同的人排在他前面,即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。
编号为 4 的人身高为 4 ,有 4 个身高更高或者相同的人排在他前面,即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 题解
图解:https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/xian-pai-xu-zai-cha-dui-dong-hua-yan-shi-suan-fa-g/
按照 身高 h 倒叙排列,若是身高一样,按照 前面高于或等于自己的人数 k 升序排序
排序后的列表为 [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
看看当前队列里有多少比自己高的
- 若是当前存在3个比自己大,但是实际上是有4个,则插入最后
- 若是当前存在3个比自己大,但是实际上是有2个,则代表 前面一定是有和自己身高相等的人,所以直接插入索引为 2 的位置可以保证不会出错。
# 示例
Python 示例
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
# 按照(0,1)的位置进行排序,代码实现的时候按高度倒叙,按人数正序排列
people.sort(key=lambda x: (-x[0], x[1]))
newQueue = []
for person in people:
if person[1] >= len(newQueue): # 是否存在比自己大的
newQueue.append(person)
else:
newQueue.insert(person[1], person)
return newQueue
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
Go 示例
func reconstructQueue(people [][]int) [][]int {
sort.Slice(people, func(a, b int) bool {
if people[a][0] == people[b][0] {
return people[a][1] < people[b][1]
}
return people[a][0] > people[b][0]
})
ans := make([][]int, 0)
for _, person := range people {
if person[1] >= len(ans) {
ans = append(ans, person)
} else {
// Python 翻译: people.insert(person[1], person)
idx := person[1]
ans = append(ans[:idx], append([][]int{person}, ans[idx:]...)...)
}
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54