拼图:找到排队的n个人的顺序(基于他们的高度)

Question

在Careercup.com上看到这个问题:

给定排在一条线上的n个人的高度和与每个人(p)相对应的数字列表,其给出高于p并站在p前面的人数.例如,

高度:5 3 2 6 1 4

InFronts:0 1 2 0 3 2

意味着实际的实际订单是:5 3 2 1 6 4

问题得到了两个高度和InFronts列表,并且应该生成排队的订单.

我的解决方案

它可以通过首先按降序排序列表来解决.显然,要进行排序,我们需要定义一个对象Person(具有Height和InFront的两个属性),然后根据它们的高度对Persons进行排序.然后,我将使用两个堆栈,一个主堆栈和一个临时堆栈来构建订单.

从最高层开始,将它放在主堆栈中.如果下一个人的InFront值大于堆叠顶部的人,则意味着应该在最顶层的人之前添加新人.因此,我们需要从主堆栈中弹出人员,插入新人员,然后返回在第一步中弹出的人员.我会使用临时堆栈来保持弹出的人的顺序.但应该弹出多少？由于列表已排序,我们需要准确地弹出新人面前的人数,即相应的InFront.

我认为这个解决方案有效.但最糟糕的情况是O(n ^ 2) - 当一个人到位时需要弹出以前的所有.

还有其他解决方案吗？可能在O(n)？

Answer 1

O（nlogn）算法是可能的。

首先假设所有高度都不相同。

按身高排序人。然后从最短到最高迭代。在每个步骤中，您都需要一种有效的方法来将下一个人放到正确的位置。请注意，我们已经放置的人并不比当前人高。而我们所追求的人比现在的人更高。因此，我们必须找到一个位置，使前面的空位置数等于此人的inFronts值。可以使用称为O（logn）时间的间隔树的数据结构来完成此任务。因此，算法的总时间为O（nlogn）。

在没有联系的情况下，该算法效果很好。可以肯定地认为，较高的人会填补前面的空旷地方。

如果可能建立联系，我们需要确保将身高相同的人按其位置的升序排列。如果我们通过不降低inFronts值来处理人员，则可以实现这一目标。因此，在可能建立联系的情况下，我们在对人员进行排序时也应考虑inFronts值。

而且，如果在某个步骤中我们找不到下一个人的职位，那么答案就是“不可能满足问题约束”。

Answer 2

我认为一种方法可以如下。尽管目前看起来又是 O(n^2) 。

按高度升序对 Height 数组和相应的“p”数组进行排序（以 O(nlogn) 为单位）。选择列表中的第一个元素。将该元素放入最终数组中由 p 索引指定的位置。

例如排序后，
H - 1, 2, 3, 4, 5, 6
p - 3, 2, 1, 2, 0, 0。

第一个元素应该位于位置 3。因此最终数组变为：
---1--

第二个元素应位于位置 2。因此最终数组变为：
--21--

第三个元素应该位于位置 1。因此最终数组变为：
-321--

第 4 个元素应位于位置 2。这是空元素中的位置。因此最终数组变为：
-321-4

第 5 个元素应位于位置 0。因此最终数组变为：
5321-4

第 6 个元素应该位于位置 0。因此最终数组变为：
532164