algorithm - 如何掌握就地数组修改算法？

Question

我正在准备软件工作面试，但在进行就地阵列修改时遇到了问题。
例如，在 out-shuffle 问题中，您将数组的两半交错，使得 1 2 3 4 5 6 7 8会变成1 5 2 6 3 7 4 8 . This question要求恒定内存解决方案(和线性时间，虽然我不确定这是否可能)。
起初我认为线性算法是微不足道的，但后来我无法解决。然后我确实找到了一个简单的O(n^2)算法，但我花了很长时间。而且我仍然没有找到更快的解决方案。
我记得在解决 Bentley 的 Programming Pearls 第 2 列中的类似问题时也遇到了麻烦:

Rotate an array left by i positions (e.g. abcde rotated by 2 becomes cdeab), in time O(n) and with just a couple of bytes extra space.

有没有人有提示可以帮助我解决这些问题？

Answer 1

大约 O(n) 时间、O(1) 空间的 out-shuffle 算法

在 O(n) 时间和 O(1) 空间内进行混洗是可能的，但它是 坚韧 .不知道为什么人们认为这很容易并建议您尝试其他方法。
下面的论文有一个 O(n) 时间和 O(1) 空间的解决方案(虽然它是用于 in-shuffle，但进行 in-shuffle 使得 out-shuffle 变得微不足道):
http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf

关于解决就地数组修改算法的方法

就地修改算法可能变得非常难以处理。
考虑一对:

在线性时间内就地洗牌。使用数论。

就地归并排序，已经开放了几年。一个算法来了，但太复杂了，不实用。使用非常复杂的簿记。

抱歉，如果这听起来令人沮丧，但没有 Elixir 可以为您解决所有就地算法问题。您需要解决问题，找出其属性，并尝试利用它们(大多数算法都是如此)。
也就是说，对于结果是原始数组排列的数组修改，您可以尝试 的方法。遵循置换循环 .基本上，任何排列都可以写成一组不相交的循环(也参见约翰的回答)。例如排列:

1 4 2 5 3 6

的 1 2 3 4 5 6可以写成

1 -> 1
2 -> 3 -> 5 -> 4 -> 2
6 -> 6.

您可以将箭头读作“前往”。
所以要置换数组 1 2 3 4 5 6你遵循三个循环:
1 到 1。
6 到 6。
2去3，3去5，5去4，4去2。
要遵循这个长周期，您只需使用一个 temp多变的。将 3 放入其中。将 2 放在 3 所在的位置。现在将 3 放入 5 并将 5 存储在 temp 中等等。由于您只使用常量 extra temp空间遵循特定循环，您正在为该循环对数组进行就地修改。
现在，如果我给你一个计算元素去向的公式，你现在需要的只是每个循环的起始元素集。
对循环起点的明智选择可以使算法变得简单。如果你想出 O(1) 空间中的起点，你现在就有了一个完整的就地算法。这就是您实际上必须熟悉问题并利用其属性的地方。
即使您不知道如何计算循环的起点，但有计算下一个元素的公式，您也可以使用此方法在某些特殊情况下获得 O(n) 时间就地算法。
例如:如果你知道无符号整数数组只包含正整数。
您现在可以遵循循环，但否定其中的数字作为“已访问”元素的指标。现在您可以遍历数组并选择您遇到的第一个正数，并遵循循环，使循环的元素为负并继续查找未触及的元素。最后，您只需再次使所有元素为正即可获得结果排列。
你得到一个 O(n) 时间和 O(1) 空间算法!当然，我们通过使用数组整数的符号位作为我们个人的“访问”位图来“欺骗”。
即使数组不一定是整数，这种方法(遵循循环，而不是符号位的 hack :-))实际上可以用来解决您陈述的两个问题:

The in-shuffle (or out-shuffle) problem :当2n+1是3的力量，可以证明(使用数论)1,3,3^2,等处于不同的循环中，所有循环都使用这些循环。将此与 in-shuffle 易于分治的事实相结合，您将获得 O(n) 时间，O(1) 空间算法(公式为 i -> 2*i modulo 2n+1 )。有关更多详细信息，请参阅上述论文。

The cyclic shift an array problem : 循环移位大小为 n 的数组来自 k还给出了结果数组的排列(由公式给出 i 到 i+k modulo n )，也可以使用以下循环方法在线性时间和原地求解。事实上，就元素交换的数量而言，这种下面的循环方法比3逆算法要好。当然，由于访问模式，遵循循环方法可以杀死缓存，而在实践中，3 反向算法实际上可能会更好。

至于面试，如果面试官是一个通情达理的人，他们会看你如何思考和处理问题，而不是你是否真的解决了问题。所以即使你没有解决一个问题，我认为你也不应该气馁。