题目
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.
题意
就是给定一个二维数组，每个元素中有两个值，第一个值代表身高，第二个表示排在前面的人中身高大于等我身高的人数。初始数组是乱序的，要求按元素中的值正确排队
例子
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]]
题解
先按照身高降序排序，遇到身高相同的则按第二个值升序排序。如例子，排好之后为
[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
此时遍历数组，对遇到的每一个元素，比较他第二个值与当前下标是否相等，不相等则要插入到他的值的下标位置，由于前面的身高都是比自己高的，所以可以直接插入到前面位置。
代码
import (
"sort"
)
func reconstructQueue(people [][]int) [][]int {
sort.Sort(People(people))
for i,p:=range people{
if i!=p[1]{
people = append(people[:i],people[i+1:]...)
temp := make([][]int,0)
temp = append(temp,people[p[1]:]...)
people = append(people[:p[1]],p)
people = append(people,temp...)
}
}
return people
}
type People [][]int
func (a People) Len() int { // 重写 Len() 方法
return len(a)
}
func (a People) Swap(i, j int){ // 重写 Swap() 方法
a[i], a[j] = a[j], a[i]
}
func (a People) Less(i, j int) bool { // 重写 Less() 方法， 从大到小排序
return (a[j][0]==a[i][0] && a[j][1]>a[i][1]) || a[j][0] < a[i][0]
}
总结
关键点在于想到排好序后，前面的都是身高比较高的，所以后面的插入到前面是没影响的。这里顺便使用了go中的排序算法，主要是重写Less方法。
