力扣406. 根据身高重建队列

下面这题的解法不仅仅让我学会了解这道题，也让我见识到了二维数组竟然还能以一行元素作为单位进行排序和遍历操作，真是学到了，学到了~~~

406. 根据身高重建队列 

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

思路：

1. 先按身高降序排序，相同身高按k升序排序，经过此次排序后高的人一定在矮的人的前面并且相同高度的人的相对顺序就是最终结果的相对顺序。请记住这两点，敲黑板

2. 创建一个集合，这个集合的每个元素是一个一维数组，也就是我们二维数组的一行。

3. 以行为单位遍历排好序的people[][]数组，假设每行数据是p[], 把每行元素插入到集合的索引为p[1]的位置，

4. 把集合中的数据转换为一个二维数组，返回即是正确结果

下面解释为什么经过第三步后就达到了我们题目要求的输出结果：

经过第一步排序后高的人一定在矮的人的前面并且相同高度的人的相对顺序就是最终结果的相对顺序，所以 在进行第三步的过程中，高的人的数据肯定是先被存入集合的，所以每当我们取出一行数据，集合中已有的元素的身高肯定都是大于等于当前元素的身高的，所以当我们取出p[]数组后，发现前面应该有p[1]个人比自己高或者高度和自己相同，那么当前元素就应该排在集合的p[1]下标的位置(仔细想想是不是)，好比说目前有一个队列的人，这些人要么比你高，要么和你一样高，现在要你插入入队中，保证你前面有p[1]个人的身高大于等于你，你是不是应该排在索引为p[1]的位置

所以经过第三步的插入操作后，把每个人都插入到了正确的位置，所以根据这个集合转换的二维数组当然就是正确结果了。

 1 class Solution {
 2     public int[][] reconstructQueue(int[][] people) {
 3         // 先按身高降序排序，相同身高按k升序排序
 4         Arrays.sort(people, new Comparator<int[]>(){        // 排序的每个元素是一个一维数组，也就是原二维数组的一行数据
 5             public int compare(int[] o1, int[] o2){         // 二维数组排序还能这么排，真是学到了，学到了
 6                 return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
 7             }
 8         });
 9 
10         // 遍历数组，把每行元素添加到一个集合的p[1]位置
11         List<int[]> list = new LinkedList<int[]>();     // 把二维数组一行元素作为一个对象
12         for(int[] p : people){
13             list.add(p[1], p);
14         }
15 
16         int n = list.size();
17         // 返回集合转换为数组的数组
18         return list.toArray(new int[n][2]); // 将集合转换成二维数组
19     }
20 }

力扣测试时间为10ms, 空间为40.9MB

复杂度分析：

时间复杂度：排序操作的时间是O(nlogn), 把一个元素插入到列表集合中的时间花费是O(k),因为需要从前往后找到第k个位置来进行插入，插入n的元素的时间复杂度为，所以最终的时间复杂度为O(n^2)

空间复杂度为列表所占空间和转化为二维数组所占空间，都是O(N), 所以空间复杂度为O(N)

思路参考：

https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode/

力扣406. 根据身高重建队列

原文：https://www.cnblogs.com/hi3254014978/p/13110391.html