algorithm - 根据高度重新排列人员的算法是否正确？

Question

给你两个数组，第一个数组包含代表人的高度的整数，第二个数组包含他面前站着的高度比他高并排成一队的人的数量。

• 高度是独一无二的，这意味着没有两个人可以有相同的高度。

例子-

答:3 2 1

乙:0 1 1

意思是高度3的人前面没有人站着，高度2的人前面有一个比他高的人，和高度1的人差不多。你的任务是安排他们 Ouput应该。 3 1 2

我的方法

1.根据频率(高人的数量)对人进行排序。

2.现在将每个人的位置固定在合适的位置。例如:

3 1 2 4

0 2 1 0

排序后

3 4 2 1

0 0 1 2

现在我们看到第一个人和第二个人在正确的位置，所以我们将第三个人移动到正确的位置，即第二个(基本索引 1)，因为他只有一个比他高。

3 2 4 1

0 1 0 2

现在对于第 4 个人，我们将它放在第 3 个位置

3 2 1 4

0 1 2 0

最终答案。

我认为它有 O(n^2) 的复杂度。我们能否做得更好，这个算法的正确性如何？

Answer 1

序列 B 最左边的值始终为 0——它是站在队列前面的人，在他之前没有人。

每当序列 B 的左侧有一系列连续的 0 时，队列的该部分将自行排序。

所以，当你有 k 个连续的 0-s 到左边和第 (k+1)-st 个位置的值 t，(t 必然 <= k)，这 k 个人中最右边的 t 比站在第 (k+1) 个位置的那个人高。

例如:假设

A: '5' '3' '6' '9' '1' '4'B: 0 0 0 2 0 1

最左边3个的高度分别是'5' < '3' < '6',

并且由于'9'的值为2，所以高度'9'的一个比最右边的 2 个比这 3 个中的另一个高。所以，只需将 '9' 向左移动 2 个位置并将其值更新为 0。

您可以使用在数组上实现的链表在O(n) 时间内解决这个问题。