LeetCode题练习与总结：根据身高重建队列--406

一、题目描述

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

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

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

• 1 <= people.length <= 2000
• 0 <= hi <= 10^6
• 0 <= ki < people.length
• 题目数据确保队列可以被重建

二、解题思路

1. 首先对数组 people 进行排序。排序规则是：首先按照身高 hi 降序排序，如果身高相同，则按照 ki 升序排序。这样做的原因是身高高的人对于身高矮的人是“不可见”的，因此我们先安排身高高的人，这样在插入身高矮的人时，就可以忽略身高高的人。

2. 创建一个空的列表 queue，用于存放最终的队列。

3. 遍历排序后的 people 数组，根据每个人的 ki 值，将其插入到 queue 中的相应位置。由于身高高的人已经先被插入，所以身高矮的人插入时，只需保证前面有 ki 个身高大于或等于他的人即可。

4. 返回 queue 作为结果。

三、具体代码

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 按照身高降序，如果身高相同则按照ki升序排序
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });

        // 创建一个空的列表用于存放最终的队列
        List<int[]> queue = new LinkedList<>();

        // 遍历排序后的people数组，根据ki值插入到队列中的相应位置
        for (int[] person : people) {
            queue.add(person[1], person);
        }

        // 将列表转换为数组并返回
        return queue.toArray(new int[people.length][2]);
    }
}

这段代码首先对 people 数组进行排序，然后创建一个 LinkedList 来模拟队列的插入操作，最后将 LinkedList 转换为数组并返回。由于 LinkedList 的 add 方法可以在指定位置插入元素，这正好符合题目中 ki 的要求。

四、时间复杂度和空间复杂度

1. 时间复杂度

• 排序操作：Arrays.sort 方法使用了双轴快速排序算法，其平均时间复杂度为 O(n log n)，其中 n 是数组 people 的长度。

• 遍历操作：对排序后的 people 数组进行遍历，这一步的时间复杂度为 O(n)。

• 插入操作：在 LinkedList 中插入元素的操作时间复杂度为 O(1)，但由于每次插入可能需要移动后续元素，因此总的时间复杂度取决于插入的位置。在最坏情况下，每次插入都发生在列表的开始位置，这样每次插入的时间复杂度将是 O(n)。因此，插入操作的总时间复杂度为 O(n^2)。

综上所述，总的时间复杂度为 O(n log n) + O(n^2) = O(n^2)，因为 O(n^2) 是主导项。

2. 空间复杂度

• 排序操作：由于在原地对数组进行排序，所以除了输入数组外，不需要额外的空间，空间复杂度为 O(1)。

• 队列操作：创建了一个 LinkedList 来存放最终的队列，其空间复杂度为 O(n)，其中 n 是数组 people 的长度。

• 返回数组：最后将 LinkedList 转换为数组，这个操作需要 O(n) 的空间来存放结果。

因此，总的空间复杂度为 O(n)，这是因为除了输入数组外，我们需要额外的空间来存储队列和最终的结果数组。

五、总结知识点

• Java 类定义：

  • class Solution 定义了一个名为 Solution 的类。

• 方法定义：

  • public int[][] reconstructQueue(int[][] people) 定义了一个公共方法 reconstructQueue，它接受一个二维整数数组 people 作为参数，并返回一个二维整数数组。

• 数组排序：

  • Arrays.sort 方法用于对数组进行排序。
  • 使用 lambda 表达式 (a, b) -> {...} 定义了一个自定义的比较器，用于排序规则。

• Lambda 表达式：

  • (a, b) -> {...} 是一个 lambda 表达式，它定义了如何比较两个数组元素。

• 逻辑运算：

  • if (a[0] == b[0]) return a[1] - b[1]; 和 return b[0] - a[0]; 中的条件判断和返回语句。

• 数据结构：

  • LinkedList<int[]> queue 创建了一个 LinkedList，用于动态地存储队列。

• 列表操作：

  • queue.add(person[1], person); 使用 LinkedList 的 add 方法在指定索引处插入元素。

• 循环遍历：

  • for (int[] person : people) 是一个增强型 for 循环，用于遍历数组 people。

• 类型转换：

  • queue.toArray(new int[people.length][2]); 将 LinkedList 转换为二维整数数组。

• 方法返回值：

  • return queue.toArray(new int[people.length][2]); 返回了重构后的队列。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。