力扣406——根据身高重建队列
- 2020 年 2 月 19 日
- 筆記
这道题主要涉及的是找规律和快速排序，优化时需要考虑 Java 中数据结构的特性。
原题
假设有打乱顺序的一群人站成一个队列。每个人由一个整数对(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]]
原题url：https://leetcode-cn.com/problems/queue-reconstruction-by-height/
解题
两次快速排序
拿到这道题目，先想想规律。关注的重点应该在于这句话：k是排在这个人前面且身高大于或等于h的人数。
所以一般肯定是 h 大的在前面，但也需要考虑 k，当 h 相同时，肯定是 k 越小，越在前面。
这样也就涉及到了排序，排序中时间复杂度低的也就是快速排序和归并排序。本题并不需要考虑稳定性，因为原始的数组并没有规律，且并没有涉及原始数组的顺序，所以两种排序用哪个都可以。但考虑到快速排序写起来更简单，因此就采用它。
我的思路是：
- 先针对 h ，如果 h 越大，则越靠前(也就是降序)，做一次快速排序。
- 如果 h 相同时，再针对 k，如果 k 越小，则越靠前(也就是升序)，再做一次快速排序。
- 利用自定义的 TreeNode 结构，也就是单向链表，根据 k 进行插入。
- 遍历单向链表，输出最终结果
接下来看看代码：
class Solution { public int[][] reconstructQueue(int[][] people) { if (people.length <= 1) { return people; } // 利用快排，针对people进行排序 // h越大，越靠前，降序 binarySort(people, 0, people.length - 1); // h相等时，k越小越靠前，升序 sortByK(people); // 构造树 TreeNode root = new TreeNode(); TreeNode temp = new TreeNode(); temp.val = people[0]; root.next = temp; for (int i = 1; i < people.length; i++) { int[] person = people[i]; // 根据k，往树中放 TreeNode preNode = root; for (int j = 0; j < person[1]; j++) { preNode = preNode.next; } // 添加节点 temp = new TreeNode(); temp.val = person; temp.next = preNode.next; preNode.next = temp; } // 最终结果 int[][] result = new int[people.length][2]; int index = 0; root = root.next; // 遍历并赋值 while (root != null) { TreeNode node = root; result[index] = node.val; root = root.next; index++; } return result; } public void sortByK(int[][] people) { int start = 0; int end = 1; int[] prePeople = people[0]; // 遍历，找出相等的结果 while (end < people.length) { // 如果两者不等 if (prePeople[0] != people[end][0]) { if (end - start >= 2) { binarySortByK(people, start, end - 1); } prePeople = people[end]; start = end; } // 如果两者相等，则什么都不需要改变 end++; } if (end - start >= 2) { binarySortByK(people, start, end - 1); } } public void binarySortByK( int[][] people, int left, int right) { // 终止条件 if (left >= right) { return; } // 标准值(待比较) int[] standard = new int[2]; standard[0] = people[left][0]; standard[1] = people[left][1]; // 提前记录 int low = left; int high = right; while (left < right) { // 先从right找起，因为left的值已经被重新存储，可以被替换 while (left < right && people[right][1] >= standard[1]) { right--; } people[left] = people[right]; // 再替换right while (left < right && people[left][1] < standard[1]) { left++; } people[right] = people[left]; } // 最终left和right必然相等 people[right] = standard; // 继续 binarySortByK(people, low, right - 1); binarySortByK(people, right + 1, high); } public void binarySort( int[][] people, int left, int right) { // 终止条件 if (left >= right) { return; } // 标准值(待比较) int[] standard = new int[2]; standard[0] = people[left][0]; standard[1] = people[left][1]; // 提前记录 int low = left; int high = right; while (left < right) { // 先从right找起，因为left的值已经被重新存储，可以被替换 while (left < right && people[right][0] < standard[0]) { right--; } people[left] = people[right]; // 再替换right while (left < right && people[left][0] >= standard[0]) { left++; } people[right] = people[left]; } // 最终left和right必然相等 people[right] = standard; // 继续 binarySort(people, low, right - 1); binarySort(people, right + 1, high); } } class TreeNode { int[] val; TreeNode next; }
提交OK，但执行时间较长，我们再优化优化。
优化
首先，针对快速排序，是否可以只用一次？答案是肯定的，我们只需要将比较条件特殊处理即可，也就是将上面两次的排序判断条件合并。
其次，针对最终结果的输出，我之前考虑用单向链表，是因为相比于数组每次插入时需要复制，链表的插入比较简单，只需要将地址换掉即可。但链表在找元素过程中耗时较长，数组可以直接利用下标计算出目标位置，且 Java 中的 ArrayList 的 add(int index, E element)，其复制方法是 native 类型，因此效率较高。所以我将最终的结果放入 ArrayList 进行处理。
接下来看看代码：
class Solution { public int[][] reconstructQueue(int[][] people) { if (people.length <= 1) { return people; } // 利用快排，针对people进行排序 binarySort(people, 0, people.length - 1); List<int[]> list = new ArrayList<>(people.length); // 根据k向ArrayList中添加元素 for (int[] person : people) { int k = person[1]; list.add(k, person); } // 转化为数组 return list.toArray(new int[people.length][2]); } public void binarySort( int[][] people, int left, int right) { // 终止条件 if (left >= right) { return; } // 标准值(待比较) int[] standard = new int[2]; standard[0] = people[left][0]; standard[1] = people[left][1]; // 提前记录 int low = left; int high = right; while (left < right) { // 先从right找起，因为left的值已经被重新存储，可以被替换 while (left < right && !compare(people[right], standard)) { right--; } people[left] = people[right]; // 再替换right while (left < right && compare(people[left], standard)) { left++; } people[right] = people[left]; } // 最终left和right必然相等 people[right] = standard; // 继续 binarySort(people, low, right - 1); binarySort(people, right + 1, high); } public boolean compare(int[] person1, int[] person2) { // h越大，越靠前，降序 int height1 = person1[0]; int height2 = person2[0]; if (height1 > height2) { return true; } if (height1 < height2) { return false; } // 当h相等时，k越小越靠前，升序 int k1 = person1[1]; int k2 = person2[1]; return k1 < k2; } }
提交OK，这样速度提升了至少一倍。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要涉及的是找规律和快速排序，优化时需要考虑 Java 中数据结构的特性。
