假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(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)方法的特性
在指定位置中插入元素，如果该位置有元素，则把该元素以及后面的所有元素后移
我们可以用元素中的第二位表示位置(先用所处的位置表示前面的人数)。
-
最高元素插入，放在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<int[]> queue = new ArrayList<>();
for (int[] p : people) {
queue.add(p[1], p);
}
return queue.toArray(new int[queue.size()][]);
}
如有写的不好的地方，还请指出^_+！
详情请参考CyC2018
网友评论