力扣406——根据身高重建队列
这道题主要涉及的是找规律和快速排序，优化时需要考虑 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 中数据结构的特性。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-02-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录