根据身高重建队列

题目链接

根据身高重建队列

题目描述

注意点

• 题目数据确保队列可以被重建
• 每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人

解答思路

• 可以先根据身高hi由高到低进行排序，然后正向遍历根据ki插入到List中的相应位置，因为身高hi由高到低进行遍历，所以当遍历到身高hi时，插入到List中ki位置可以保证前面的身高都比当前身高hi高，也就是前面正好有ki个身高大于或等于hi的人，保证是根据身高重建队列
• 注意根据身高hi由高到低进行排序时，会有身高相等的情况，但是其ki一定不同，又因为每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人，所以排序时当两个身高相同，还要根据ki由小到大进行排序，保证前面的元素先插入到List中（不会影响未插入身高的队列）

代码

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] people1, int[] people2) {
                if (people1[0] != people2[0]) {
                    return people2[0] - people1[0];
                }
                return people1[1] - people2[1];
            }
        });
        List<int[]> res = new ArrayList<>(people.length);
        for (int[] person : people) {
            res.add(person[1], person);
        }
        return res.toArray(new int[people.length][2]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

关键点

• 一般这种数对，还涉及排序的，根据第一个元素正向排序，根据第二个元素反向排序，或者根据第一个元素反向排序，根据第二个元素正向排序，往往能够简化解题过程
• 根据身高由高到低进行排序，如果身高相同，则根据ki由小到大进行排序
• List中add(int index, int element)方法将指定元素插入到相应位置，如果该位置已经有元素，则替代该元素，且将该位置及其后面的元素都向后移动一位
• List转为数组的方法