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
1
Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
2
​
3
Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
Copied!
2. Implementation
(1) Sorting 
思路:
(1) 根据题意，我们发现两点:1.最矮的人不会影响其他人的位置, 2. 在最矮的人群中，k的值最高的那个人不会影响其他人的位置。
(2) 基于这两点，我们可以将输入数组按照以下规则排序，先按高度从高到低排， 如果高度相同，则将index(第二个元素)的数从小到大排，排好序后，第二个元素则为该数组所处的位置
1
class Solution {
2
    public int[][] reconstructQueue(int[][] people) {
3
        Arrays.sort(people, new Comparator<int[]>() {
4
            @Override
5
            public int compare(int[] a, int[] b) {
6
                return a[0] == b[0] ? a[1] - b[1] : b[0] - a[0];
7
            }
8
        });
9
​
10
        List<int[]> list = new ArrayList<>();
11
​
12
        for (int[] info : people) {
13
            list.add(info[1], info);
14
        }
15
​
16
        int[][] res = new int[people.length][2];
17
​
18
        for (int i = 0; i < people.length; i++) {
19
            res[i][0] = list.get(i)[0];
20
            res[i][1] = list.get(i)[1];
21
        }
22
        return res;
23
    }
24
}
Copied!
(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)
1
class Solution {
2
    class TreeNode {
3
        int leftCount;
4
        int[] people;
5
        TreeNode left, right;
6
​
7
        public TreeNode(int[] people) {
8
            this.people = people;
9
            leftCount = 1;
10
            this.left = null;
11
            this.right = null;
12
        }
13
    }
14
​
15
    public int[][] reconstructQueue(int[][] people) {
16
        int[][] res = new int[people.length][2];
17
​
18
        if (people == null || people.length == 0) {
19
            return res;
20
        }
21
​
22
        Arrays.sort(people, new Comparator<int[]>(){
23
            @Override
24
            public int compare(int[] a, int[] b) {
25
                return a[0] == b[0] ? a[1] - b[1] : b[0] - a[0];
26
            }
27
        });
28
​
29
        TreeNode root = new TreeNode(people[0]);
30
        for (int i = 1; i < people.length; i++) {
31
            insert(root, new TreeNode(people[i]), people[i][1]);
32
        }
33
​
34
        inorderTraverse(root, res);
35
        return res;
36
    }
37
​
38
    public void insert(TreeNode root, TreeNode newNode, int k) {
39
        TreeNode curNode = root;
40
​
41
        while (curNode != null) {
42
            if (k < curNode.leftCount) {
43
                ++curNode.leftCount;
44
                if (curNode.left == null) {
45
                    curNode.left = newNode;
46
                    break;
47
                }
48
                else {
49
                    curNode = curNode.left;
50
                }
51
            }
52
            else {
53
                if (curNode.right == null) {
54
                    curNode.right = newNode;
55
                    break;
56
                }
57
                else {
58
                    k -= curNode.leftCount;
59
                    curNode = curNode.right;
60
                }
61
            }
62
        }
63
    }
64
​
65
    public void inorderTraverse(TreeNode root, int[][] res) {
66
        Stack<TreeNode> stack = new Stack();
67
        TreeNode curNode = root;
68
        int index = 0;
69
​
70
        while (curNode != null || !stack.isEmpty()) {
71
            if (curNode != null) {
72
                stack.push(curNode);
73
                curNode = curNode.left;
74
            }
75
            else {
76
                curNode = stack.pop();
77
                res[index] = curNode.people;
78
                ++index;
79
                curNode = curNode.right;
80
            }
81
        }
82
    }
83
}
Copied!
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)

409 Longest Palindrome

370 Range Addition

Last modified 2yr ago

Copy link

Contents

406. Queue Reconstruction by Height

1. Question

2. Implementation

3. Time & Space Complexity

406. Queue Reconstruction by Height​

1. Question

2. Implementation

3. Time & Space Complexity

406. Queue Reconstruction by Height