leetcode 406. 根据身高重建队列

题解

首先进行排序,身高从高到低,同时根据前面有几个人从低到高,排好之后,根据前面有几人依次插入到相应位置

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
type Sorter [][]int

func (sorter Sorter) Len() int { return len(sorter) }
func (sorter Sorter) Swap(i, j int) { sorter[i], sorter[j] = sorter[j], sorter[i] }
func (sorter Sorter) Less(i, j int) bool {
if (sorter[i][0] == sorter[j][0]) {
return sorter[i][1] < sorter[j][1]
} else {
return sorter[i][0] > sorter[j][0]
}
}

func reconstructQueue(people [][]int) [][]int {
res := make([][]int, 0)
sorter := Sorter(people)
sort.Sort(sorter)
for _, v := range sorter {
res = append(res, nil)
copy(res[v[1]+1:], res[v[1]:])
res[v[1]] = v
}
return res
}