LeeCode 406根据身高重建队列解析

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

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]]

首先

我们把这个数组按身高降序排列，重复的部分按k升序排列

排序后的数组
7，0
7，1
6，1
5，0
5，2
4，4

思路

假设有一个空队列

我们先把身高最高的插入，并且它的第二位一定为0

接下来我们把次高的元素插入合适的位置，这个元素无论放到队列中的哪个位置(最高元素的前面或者后面)，
对原队列中元素的第二位没有任何影响(同时又能放入合适的位置)，
因为原队列中的元素都比它高，所以不会改变原数组的第二位。

以此进行，把次次高的元素插入合适位置，同时又不会对原队列产生影响。

java实现

接下来我们选择数组中身高最高的元素插入到List中

首先我们来看一下List.add(int index, E element)方法的特性

在指定位置中插入元素，如果该位置有元素，则把该元素以及后面的所有元素后移

我们可以用元素中的第二位表示位置(先用所处的位置表示前面的人数)。

1. 最高元素插入，放在0位置。

2. 次高元素插入:

    if(第二位为i==原队列中的某个元素第二位){
        重叠元素以及后面的元素都后移        
        放在i位置(也就是说放在0位置，最高元素后移)
        //保证了这个新来的元素的位置表示前面的人数
    }else{
        //如果第二位为i
        放i位置
    }

3. 以此进行，便可得到排序后的队列。

//来自cyc2018
public int[][] reconstructQueue(int[][] people) {
    if (people == null || people.length == 0 || people[0].length == 0) {
        return new int[0][0];
    }
    Arrays.sort(people, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
    List<int[]> queue = new ArrayList<>();
    for (int[] p : people) {
        queue.add(p[1], p);
    }
    return queue.toArray(new int[queue.size()][]);
}

如有写的不好的地方，还请指出^_+！
详情请参考CyC2018