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]] 是重新构造后的队列。
题解
-
按照 身高 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
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
}