如何用O(1)辅助空间将数组排列成给定的顺序？
如何实现以下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元素进行排序呢？
P.S.：这不是考试题，我实际上需要这个功能。
CLARIFICATION:似乎对元素的最终顺序存在误解。示例中的结果数组应该具有以下元素，引用原始的chars数组：
{chars[2], chars[4], chars[3], chars[0], chars[1]}这就是
{'c', 'e', 'd', 'a', 'b'}. 回答 6
Stack Overflow用户
发布于 2009-09-27 13:47:23
严格地说，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)时间。
Stack Overflow用户
发布于 2009-09-27 13:49:24
不可能。
您至少需要O(log (列表大小))才能知道排序元素的索引。
Stack Overflow用户
发布于 2009-09-27 19:08:55
这将完成O(n²)中的工作。在外部循环的每一次迭代中，当前想要的元素被交换到其正确的位置(第一个内环)，然后调整其余元素的想要的顺序以反映新的情况(第二个内环)。
for (int i = 0; i < length; i++)
{
for (int j = wantedOrder[i]; j > i; j--)
{
Swap(chars, j, j - 1);
}
for (int j = i + 1; j < length; j++)
{
if (wantedOrder[j] < wantedOrder[i])
{
wantedOrder[j]++;
}
}
}当然，这需要销毁想要的订单数组。如果这是不允许的，我不知道如何解决这个问题(至少目前是这样)。
https://stackoverflow.com/questions/1484538
复制相似问题
腾讯云开发者
