使用特殊 属性 对数组进行排序

Question

有一个数组 A 具有以下 属性:

对于 A 中的每个 x,y，如果 x < y 则 x 在 A 中的首次出现早于 y 在 A 中的首次出现。

如何在平均 O(n) 的时间里稳定排序数组 A。

我正在准备数据结构考试，我在尝试解决过去的考试时遇到了这个问题。

Answer 1

由于 A 的 属性 你知道所有元素的第一次出现已经形成一个排序列表。其他事件需要在它们各自第一次出现后按输入顺序直接结束（因为你想要一个稳定的排序）。

您需要跟踪列表中最先出现的内容。您需要在哈希映射中跟踪从元素到元素列表的后续事件。最后，您可以遍历第一次出现的列表，并在进行时从哈希图中收集列表。

在伪代码中类似于：

list: List(Element)
map: Map(Element -> List(Element))

foreach x in A
    if x exists in map
        map[x].add(x)
    else
        map.[x] = [x]
        list.add(x)

result = []
foreach x in list
    result.concat(map[x])