贪心算法---根据身高重建队列
题目:
假设有打乱顺序的一群人站成一个队列,数组 people
表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [hi, ki]
表示第 i
个人的身高为 hi
,前面 正好 有 ki
个身高大于或等于 hi
的人。
请你重新构造并返回输入数组 people
所表示的队列。返回的队列应该格式化为数组 queue
,其中 queue[j] = [hj, kj]
是队列中第 j
个人的属性(queue[0]
是排在队列前面的人)。
思路:
先考虑身高,再考虑人数。将数组按照身高降序排列,身高相同的按照人数升序排列。将排好序的people数组元素一个一个插入到队列中,ki就是该元素的下标。
代码:
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people,(a,b)->{
if(a[0]==b[0]) return a[1]-b[1];//如果身高相等,按照k升序排列
return b[0]-a[0];//按照身高降序排列
});
LinkedList<int[]> que=new LinkedList<>();
for(int[] p:people){
que.add(p[1],p);//将p插入到下标为p[1]的位置上
}
return que.toArray(new int[people.length][]);
}