如何使用O(1)辅助空间将数组置换为给定的顺序？

Question

如何实现以下OrderElements功能？

char chars[] = {'a', 'b', 'c', 'd', 'e'};
int want_order[] = {2, 4, 3, 0, 1};
int length = 5;
OrderElements(chars, want_order, length);

// chars now contains: c, e, d, a, b

当您可以使用线性额外空间时很容易,但是只能使用恒定的额外空间,即直接对chars元素进行原位排序吗？

PS:这不是考试问题; 我实际上需要这个功能.

澄清:似乎存在对所需元素最终顺序的误解.示例中的结果数组应该具有以下元素,引用原始chars数组:

{chars[2], chars[4], chars[3], chars[0], chars[1]}

是的

{'c', 'e', 'd', 'a', 'b'}. 

Answer 1

但是,严格地说,O(lg length)需要内存来表示列表索引; 但是,我将在本次讨论中忽略这一点,因为使用64位i可能足以满足我们实际可以重新排序的任何内容.

for (int i = 0; i < length; i++) {
  int t = want_order[i];
  while (t < i) {
    // t has been moved already; we need to find out where the value that started there
    // went. Since we must've put it at want_order[t] before, resume looking there
    t = want_order[t];
    // once t >= i, we know we've not touched that slot more than once, and so our
    // value is there
  }
  swap(chars[i], chars[t]);
}

一个直观的解释:对于数组中的每个项目,我们将目标值放入其中,将旧值存储在包含我们目标值的插槽中.我们必须注意处理我们的目标价值被取代的情况; 通过注意给定的插槽最多只交换两次来处理; 一旦当其中的值被另一个值(这不可能发生,因为这个迭代将要这样做)或当值被移位以插入最终值(仅发生在较低的索引)时.

举例说明了如何查看示例数据:

 i | want_order | chars     | t
 0 |  2 4 3 0 1 | a b c d e | 2 (swap)
 1 |  2 4 3 0 1 | c b a d e | 4 (swap)
 2 |  2 4 3 0 1 | c e d a b | 3 (swap)
 3 |  2 4 3 0 1 | c e d a b | 0 (follow)
 3 |  2 4 3 0 1 | c e d a b | 3 (swap - no-op)
 4 |  2 4 3 0 1 | c e d a b | 1 (follow)
 4 |  2 4 3 0 1 | c e d a b | 4 (swap - no-op)

该算法仅使用O(lg n)内存(用于索引),但我没有尝试完全分析其运行时间.很明显,这是最糟糕的O(n^2),但我怀疑它会比实际情况更好.然而,它可能必须遵循的链的长度没有实际限制,因此原则上它实际上可能最终使用O(n^2)最坏情况输入的时间.