【LeetCode】406. 根据身高重建队列

我的直观思路是搜索回溯算法，加上剪枝。也就是dfs，深度优先遍历。

但是最终的结果是超出时间限制，看来需要换一种耗时少的算法。

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 用搜索回溯的方法来解题。
        int len = people.length;// 一共有len个人
        int count = 0; // 排序到第count个人
        LinkedList<int[]> path = new LinkedList<>();// 保存路径。
        int[][] res = new int[len][2];// 存储结果
        boolean[] mark = new boolean[len];
        dfs(people, len, count, path, res, mark);
        return res;
    }

    /**
     *
     * @param people 原始的数组。
     * @param len    原始数组的长度
     * @param count  排序到第count个人
     * @param path   保存路径
     * @param res    存储结果
     * @param mark   标记是否放到path中
     */
    private void dfs(int[][] people,
                     int len,
                     int count,
                     LinkedList<int[]> path,
                     int[][] res,
                     boolean[] mark) {
        if (count == len) {// 最后一个了，可以保存结果退出了
            for (int i = 0; i < len; i++) {
                res[i][0] = path.get(i)[0];
                res[i][1] = path.get(i)[1];
            }
            return;
        }

        // 进行遍历
        for (int i = 0; i < len; i++) {
            int[] tmp = people[i]; // 获取第i个人的信息。
            if (mark[i]) {// 说明已经在path中了
                continue;
            }
            int sum = 0;
            int height = tmp[0];//这个人的身高
            for (int[] ints : path) {
                if (ints[0] >= height) {
                    sum++;
                }
            }
            if (sum != tmp[1]) {// 不满足身高计数，continue
                continue;
            }
            // 没在path中，并且满足身高计数
            mark[i] = true;
            path.add(tmp);
            count++;
            dfs(people, len, count, path, res, mark);
            count--;
            path.removeLast();
            mark[i] = false;
        }

    }
}

思路很新奇。对高个子人来说，“看不见”矮个子的人。所以先排序 高个子的人， 然后将矮个子的人插入其中。

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 思路很新奇。对高个子人来说，“看不见”矮个子的人。
        // 所以先排序 高个子的人， 然后将矮个子的人插入其中。
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] arr1, int[] arr2) {
                if (arr1[0] == arr2[0]) {// 如果身高相同，按照第二个数值排序
                    return arr1[1] - arr2[1];
                } else {// 如果身高不同，按照身高的降序排列
                    return arr2[0] - arr1[0];
                }
            }
        });
        // 现在已经排序完成。然后进行， 插队就可以了。
        int len = people.length;
        for (int i = 0; i < len; i++) {// 遍历这个数组
            if (people[i][1] == i) {// 如果序号 一致 的话，就不用插队了
                continue;
            } else {// 说明要进行插队
                int height = people[i][0];
                int index = people[i][1];
                for (int j = i - 1; j >= index; j--) {// 这些序号的都需要 向后移动一个位置
                    people[j + 1][0] = people[j][0];
                    people[j + 1][1] = people[j][1];
                }
                people[index][0] = height;
                people[index][1] = index;
            }
        }


        return people;
    }
}

我这里写的方法中，自己实现，插队。但是其实LinkedList中 void add(int index, E element) 可以实现插队。时间又有所优化。

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 思路很新奇。对高个子人来说，“看不见”矮个子的人。
        // 所以先排序 高个子的人， 然后将矮个子的人插入其中。
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] arr1, int[] arr2) {
                if (arr1[0] == arr2[0]) {// 如果身高相同，按照第二个数值排序
                    return arr1[1] - arr2[1];
                } else {// 如果身高不同，按照身高的降序排列
                    return arr2[0] - arr1[0];
                }
            }
        });
        // 现在已经排序完成。然后进行， 插队就可以了。
        LinkedList<int[]> list = new LinkedList<>();
        for (int[] person : people) {
            list.add(person[1], person);
        }
        return list.toArray(new int[people.length][2]);
    }
}