Google
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)