根据步骤合并排序后恢复原始数组

Question

我正在尝试编写一种算法来从已排序的数组重建原始数组。考虑输入值是一个由 1 和 2 组成的字符串，其中 1 表示在合并排序的合并部分中，选择左子数组中的元素，2 表示选择右子数组中的元素。 我该怎么做？特别是我在合并排序将子数组剩下的内容附加到最终列表的部分上遇到问题。 例如：在数字数组 [1,2,3,4] 上给出 12212 作为输入字符串。这意味着数字 1 到 4 存在一个排列，如果将其进行合并排序，它将给出 12212。该排列是 2 4 3 1 。

Answer 1

当您记录合并步骤时，您将获得足够的 1 秒来消耗整个左侧数组，或者获得足够的 2 秒来消耗整个右侧数组。对于 2+2 合并，有以下几种可能性：

11
121
122
211
212
22

这组字符串始终是无前缀，这意味着如果您知道合并序列从哪里开始，那么您就可以知道它在哪里结束。

不幸的是，它不是无后缀。例如，它包括

22

和

122

。这意味着你无法通过知道它的结束位置来判断它的开始位置。例如，如果您的字符串以

...1122

结尾，并且您知道它以 2+2 合并结尾，则它可能是

22

合并或

122

合并。如果不从一开始就跟踪所有合并，就无法区分差异。

这使得编写取消合并排序函数有点棘手，因为您必须从步骤记录字符串的开头开始。

事实上，取消合并的最简单方法是：

1. 制作一个从 0 到 n-1 的数字的排序数组
2. 对数组进行合并排序，但使用索引字符串而不是比较
3. 现在您有了一个数组，它将每个位置映射到最终到达该位置的元素的原始索引。使用它可以在 O(n) 时间内撤消排序。