存在一种平均复杂度为 O(nlogn) 的算法，但最坏情况下的复杂度仍然为 O(n²)。
为此，您可以使用二叉树的变体。这个想法是，在这棵树中，每个节点对应一个人，每个节点在插入节点时跟踪他前面有多少人（这是左子树的大小）。
开始以高度递减的顺序迭代 people 数组，并从根开始将每个人插入到树中。插入如下：
- 将
frontCount人的值与当前节点的（开头的根）值进行比较。
- 如果它小于它，则将值为 1 的节点插入左侧。将当前节点的值增加 1。
frontCount否则，通过将人的值减少当前节点的值来向右下降。这使节点能够放置在正确的位置。
在所有节点完成后，中序遍历给出正确的人员顺序。
让代码自己说话：
public static void arrange(int[] heights, int[] frontCounts) {
Person[] persons = new Person[heights.length];
for (int i = 0; i < persons.length; i++)
persons[i] = new Person(heights[i], frontCounts[i]);
Arrays.sort(persons, (p1, p2) -> {
return Integer.compare(p2.height, p1.height);
});
Node root = new Node(persons[0]);
for (int i = 1; i < persons.length; i++) {
insert(root, persons[i]);
}
inOrderPrint(root);
}
private static void insert(Node root, Person p) {
insert(root, p, p.frontCount);
}
private static void insert(Node root, Person p, int value) {
if (value < root.value) { // should insert to the left
if (root.left == null) {
root.left = new Node(p);
} else {
insert(root.left, p, value);
}
root.value++; // Increase the current node value while descending left!
} else { // insert to the right
if (root.right == null) {
root.right = new Node(p);
} else {
insert(root.right, p, value - root.value);
}
}
}
private static void inOrderPrint(Node root) {
if (root == null)
return;
inOrderPrint(root.left);
System.out.print(root.person.height);
inOrderPrint(root.right);
}
private static class Node {
Node left, right;
int value;
public final Person person;
public Node(Person person) {
this.value = 1;
this.person = person;
}
}
private static class Person {
public final int height;
public final int frontCount;
Person(int height, int frontCount) {
this.height = height;
this.frontCount = frontCount;
}
}
public static void main(String[] args) {
int[] heights = {5, 3, 2, 6, 1, 4};
int[] frontCounts = {0, 1, 2, 0, 3, 2};
arrange(heights, frontCounts);
}