406. 根据身高重建队列

打卡!!!每日一题

今天想通过一道题给大家分享一下一些常见的但是你却不一定了解的知识。

题目描述：

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

题目示例：

这道题的意思大致就是说我们要重新给这个队列排一下序保证其位置就是真实的排队顺序。

个矮的对个高的没影响，因为个矮的一定排在个高的后面，所以我们可以按照身高从个高到个矮的往下排序。

说到排序，我就不得不要和大家分享一下Comparator接口的用法。

如：一个数组里有以下元素：[3 , 4 , 1 , 9 , 0 , 7 ]

String[] nums = {"3", "4", "1", "9", "0", "7"};
        Arrays.sort(nums, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        });
1
2
3
4
5
6
7

我简单说2个要点：
要点1：Comparator接口的使用

• o1.compareTo(o2)：
  • 正数：o1>o2
  • 零：o1=o2
  • 负数：o1
• compare(String o1, String o2)中o1：表示后一个值，o2表示前一个值，当且仅当compare函数返回值小于0时才进行前后的交换
  • 如：3,4 则o1:4,o2:3
    4.compareTo(3)，其结果是大于0的则不进行任何操作，
  • 再比如：4，1； 1.compareTo(4)小于0,则对数组nums中的4和1的位置进行交换，同时在和前面的3比，1.compareTo(3)小于0，则对数组nums中的1和3的位置进行交换，依此类推。

如果想要倒序，只需要将o2与o1的位置更换即可，改为：o2.compareTo(o1);我们还是以3 4 1这三个数为例，我们知道o1表示后一个数，o2表示前一个数，3.compareTo(4)小于0，交换3和4的位置，变成4 3 1，再接着往后比：3.compareTo(1)大于0，无需操作，于是最终的结果为4 3 1

要点2：List的使用
如List ans = new ArrayList<>();
ans.add(0,1)
ans.add(0,2)
我在0号为插入两个数值，怎么办呢？

很多人是不是认为我会把原来的1覆盖掉变成2呢，其实不是，而是按照队列的方式，即先进先出，把最新的元素放在队头。

举个例子：原来ans里面有：1,2,3
现在我进行ans.add(0,-1)的操作，则ans就会变成：-1,1,2,3

ans.add(1,5)，则ans就会变成：1,5,2,3

所以有了以上基础知识作为支撑，我们就可以将排好序的身高列表，依次放在一个list里，我们以题目示例1为例:[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

按照身高由大到小的排序：[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

然后将其按照对应的下标进行存放即可

List<int[]> ans = new ArrayList<int[]>();
        for (int[] person : people) {
            ans.add(person[1], person);
        }
1
2
3
4

最终代码如下：

import java.util.*;
public class 根据身高重建队列_406 {

    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] person1, int[] person2) {
                if (person1[0] != person2[0]) {
                    return person2[0] - person1[0];
                } else {
                    return person1[1] - person2[1];
                }
            }
        });
        List<int[]> ans = new ArrayList<int[]>();
        for (int[] person : people) {
            ans.add(person[1], person);
        }
        return ans.toArray(new int[ans.size()][]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20