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

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

Input
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output
【LeeCode|LeeCode 406根据身高重建队列解析】[[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)方法的特性

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

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

最高元素插入，放在0位置。
次高元素插入:

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

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

//来自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 queue = new ArrayList<>(); for (int[] p : people) { queue.add(p[1], p); } return queue.toArray(new int[queue.size()][]); }

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