leetcode 406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意：
总人数少于1100人。

示例

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

func reconstructQueue(people [][]int) [][]int {
    //peolpe[i]第一个属性是身高h, 第二个属性是k, k表示people[i]前面身高大于或等于h的人数
    //思路： 先排序后插入, 先对乱序的二维切片按第一个属性h降序，第二个属性k升序排序
    //排序后，因为people[i]前面的身高h都是大于或等于people[i]的, 所以将people[i][1]为k的数据插入到位置k即可

    // 先排序
    // [7,0], [7,1], [6,1], [5,0], [5,2], [4,4]

    // 再一个一个插入。
    // [7,0]
    // [7,0], [7,1]
    // [7,0], [6,1], [7,1]
    // [5,0], [7,0], [6,1], [7,1]
    // [5,0], [7,0], [5,2], [6,1], [7,1]
    // [5,0], [7,0], [5,2], [6,1], [4,4], [7,1]

    length := len(people)

    //根据二维切片的第一个属性从大到小排序，第二个属性默认是递增顺序
    less := func(i, j int) bool {
        if people[i][0] == people[j][0] {
            return people[i][1] < people[j][1]
        }
        return people[i][0] > people[j][0]
    }
    //调用排序函数
    sort.Slice(people, less)
    //当前该插入序号为i的数据了
    i := 0
    for i < length {
        CurPeople := people[i]
        k := CurPeople[1]
        if k < i {
            //从后往前遍历，将序号为i到k+1的数据，进行「插队」步骤的元素交换
            for j := i; j > k; j-- {
                people[j] = people[j-1]
            }
            //将people[i][1]为k的数据放入序号k位置上
            people[k] = CurPeople
        }
        i++
    }
    return people
}

leetcode 406. 根据身高重建队列

原文：https://www.cnblogs.com/nyist-xsk/p/11365303.html