刷leetcode——根据身高重建队列 身高重塑规律

这道题主要涉及的是找规律和快速排序，优化时需要考虑 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 中数据结构的特性。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。

https://death00.github.io/

公众号：健程之道