Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.
Note: The number of people is less than 1,100.
Example
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]]
分析：首先按照身高从小到大的顺序排序，身高相同的则根据其前面大于等于其的人数从小到大的顺序排序；
身高相同的其相对顺序已确定；
首先将身高最高的索引列表，依次将身高第二高/第三高...的根据其前面比其高的人数插入列表，插入索引就是其前面比其高的人数。
实现时，先排序，同时存储在列表中的是索引；然后再根据此列表对应的数组中的第二个元素值作为索引插入新列表中，此时新列表中的索引即是排好序的索引。
public class Solution { public int[][] reconstructQueue(int[][] people) { int n=people.length; List<Integer> list=new ArrayList<Integer>();//保存索引 list.add(0); //sort the array，先按照身高从大到小， 然后再按其前面的人数从小到大 for(int i=1;i<n;i++){ int j=0; for(;j<i;j++){ int index=list.get(j); if(people[i][0]>people[index][0]){ list.add(j,i); break; }else if(people[i][0]==people[index][0]){ int k=j; while(k<list.size()&&people[i][0]==people[list.get(k)][0]){ if(people[i][1]<people[list.get(k)][1]){ list.add(k,i); break; } k++; } if(k==list.size()) list.add(i); else if(people[i][0]!=people[list.get(k)][0]){ list.add(k,i); } break; } } if(j==list.size()) list.add(i); } List<Integer> list1=new ArrayList<Integer>(); // 根据排序后的元素的位置插入 int i=0; for(;i<n;i++){ int index=people[list.get(i)][1]; if(index<list1.size()) list1.add(index,list.get(i)); else list1.add(list.get(i)); } int[][] res=new int[n][2]; for(i=0;i<n;i++){ res[i][0]=people[list1.get(i)][0]; res[i][1]=people[list1.get(i)][1]; } return res; } }
