406 Queue Reconstruction by Height

406. Queue Reconstruction by Height

1. Question

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers(h, k), wherehis the height of the person andkis the number of people in front of this person who have a height greater than or equal toh. Write an algorithm to reconstruct the queue.

Note: The number of people is less than 1,100.

Example

Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

2. Implementation

(1) Sorting

思路:

(1) 根据题意，我们发现两点:1.最矮的人不会影响其他人的位置, 2. 在最矮的人群中，k的值最高的那个人不会影响其他人的位置。

(2) 基于这两点，我们可以将输入数组按照以下规则排序，先按高度从高到低排， 如果高度相同，则将index(第二个元素)的数从小到大排，排好序后，第二个元素则为该数组所处的位置

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] == b[0] ? a[1] - b[1] : b[0] - a[0];
            }
        });

        List<int[]> list = new ArrayList<>();

        for (int[] info : people) {
            list.add(info[1], info);
        }

        int[][] res = new int[people.length][2];

        for (int i = 0; i < people.length; i++) {
            res[i][0] = list.get(i)[0];
            res[i][1] = list.get(i)[1];
        }
        return res;
    }
}

(2) Binary Search Tree

1.第一步还是先对people数组排序，将高的排在前面，同样高度的话按照第二元素的值升序排。

2.第二步自定义Binary Search Tree， treeNode包含leftCount代表对当前node里的这个人有多少人是比他高。由于我们是按照高度从高到矮插入bst中，所以对于当前要插入的node(这个node代表的人的高度必然不比当前bst每个node个高度高)，如果它的k值(每个数组第二个元素)比curNode的leftCount小，说明curNode代表的人的高度不会影响要插入node的位置，所以node要在curNode的左边，否则node要在curNode右边，注意在右边的话, k值要减去curNode.leftCount，因为在插入bst的过程中，我们已经知道有多少人比要插入node的人的高度高。

3.最后对bst做一个inorder traversal，得到最后结果

4.这种方法有机会将时间复杂度从O(n^2)降为O(nlogn),但由于树不能保证是balanced的，所以最坏情况还是O(n^2)

class Solution {
    class TreeNode {
        int leftCount;
        int[] people;
        TreeNode left, right;

        public TreeNode(int[] people) {
            this.people = people;
            leftCount = 1;
            this.left = null;
            this.right = null;
        }
    }

    public int[][] reconstructQueue(int[][] people) {
        int[][] res = new int[people.length][2];

        if (people == null || people.length == 0) {
            return res;
        }

        Arrays.sort(people, new Comparator<int[]>(){
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] == b[0] ? a[1] - b[1] : b[0] - a[0];
            }
        });

        TreeNode root = new TreeNode(people[0]);
        for (int i = 1; i < people.length; i++) {
            insert(root, new TreeNode(people[i]), people[i][1]);
        }

        inorderTraverse(root, res);
        return res;
    }

    public void insert(TreeNode root, TreeNode newNode, int k) {
        TreeNode curNode = root;

        while (curNode != null) {
            if (k < curNode.leftCount) {
                ++curNode.leftCount;
                if (curNode.left == null) {
                    curNode.left = newNode;
                    break;
                }
                else {
                    curNode = curNode.left;
                }
            }
            else {
                if (curNode.right == null) {
                    curNode.right = newNode;
                    break;
                }
                else {
                    k -= curNode.leftCount;
                    curNode = curNode.right;
                }
            }
        }
    }

    public void inorderTraverse(TreeNode root, int[][] res) {
        Stack<TreeNode> stack = new Stack();
        TreeNode curNode = root;
        int index = 0;

        while (curNode != null || !stack.isEmpty()) {
            if (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }
            else {
                curNode = stack.pop();
                res[index] = curNode.people;
                ++index;
                curNode = curNode.right;
            }
        }
    }
}

3. Time & Space Complexity

Sorting: 时间复杂度O(nlogn + n^2) => O(n^2), 空间复杂度O(n), n为people数组的长度

Binary Tree: 时间复杂度：平均O(nlogn)，最坏O(n^2)， 空间复杂度O(n)