题目描述

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(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]]

排序

时间复杂度：O(N^2) 排序使用了 O(NlogN) 的时间 空间复杂度：O(N)

class Solution { public int[][] reconstructQueue(int[][] people) { Arrays.sort(people, new Comparator<int[]>() { public int compare(int[] a, int[] b) { if(a[0]==b[0]){ return a[1] - b[1]; }else { return b[0] - a[0]; } } }); List<int[] > list = new LinkedList<>(); for(int[] p : people){ list.add(p[1],p); } return list.toArray(new int[people.length][2]); } }

第二种写法

class Solution { public int[][] reconstructQueue(int[][] people) { Arrays.sort(people,(int[] a,int[] b) -> a[0]==b[0]?a[1]-b[1]:b[0]-a[0] ); List<int[] > list = new LinkedList<>(); //ArrayList和LinkedList在同一个位置加入元素后 先加入的会被挤到后面 for(int[] p : people){ list.add(p[1],p); } return list.toArray(new int[people.length][2]); } }