能否使用常量内存开销来重新排列一个数组？

Question

能否使用常量内存开销来重新排列一个数组？

6

我在阅读一些StackOverflow的问题时偶然发现了这个问题，但没有找到一个令人满意的答案。

假设我们有一个长度为n的数组A，其中包含它的索引从0到n-1的随机排列。是否可能重新排列数组，使其结果为A[A[i]]，并且需要常数O(1)内存开销？

例子：

A = [ 3, 2, 0, 1 ]
rearrange( A )
A = [ 1, 0, 3, 2 ]

如果可能的话，提供算法概述会很好。否则，请解释为什么不可能。由于原地排序是一件事情，因此这个问题可能类似。

澄清：如果您没有内存限制，该算法就很简单：

A = [ 3, 2, 0, 1 ]
A_r = Array_of_size( A )
for i = 0 to Arraysize - 1
   A_r[ i ] = A[ A[i] ]

结果 A_r = [1, 0, 3, 2]

- Taron

3

重排数组的逻辑是什么？ - Hassan Imam

1

当然，你可以就地重新排列数组（维基百科）。编写逻辑取决于你，但你不需要额外的数组。 - hellow

4

在这种特定情况下，在原地重新排列数组似乎并不那么明显。 - Denys Séguret

2

事实上，解决方案（如果存在的话，我有所怀疑）并不是微不足道的。我会淘汰语言技巧，因为在我看来，在值中找到一个自由位与使用数组的O(n)片段等价。 - m.raynal

1

@m.raynal 对于这个技巧，我指的是当可以从值类型或已知值范围中确定自由位时的情况。当然，在一般情况下这不是一个答案，我也不会将其写成一个答案。但是，大多数实际出现的这种问题并不完全是这样，并且可以在实践中使用这个技巧来解决。 - Denys Séguret

显示剩余3条评论

2个回答

2

如果我们结合基于孔的链交换，并且可以通过数组中最低或最高位置识别排列中的循环，那么确实是可能的。对于每个位置，只有在该位置是循环中最高位置时，我们才会通过该循环进行链接。基于孔的方法确保我们仅使用恒定的空间来执行循环的旋转。缺点是时间复杂度变为O(n^2)。以下是一个简单的Python实现：

def is_start(array, index):
    start = index
    index = array[index]
    while start > index:
        index = array[index]
    return start == index


def rotate(array, index):
    start = index
    next = array[index]
    hole = next
    while start > next:
        array[index] = array[next]
        index = next
        next = array[index]
    array[index] = hole


def rearrange(array):
    for index in range(len(array)):
        if is_start(array, index):
            rotate(array, index)

修复Bug

(@trincot) 指出，使用循环的最后一个条目而不是第一个条目可以确保我们永远不会调查可能已损坏的循环。效果：将不等式的方向从 start < index 更改为 start > index。

- Ninetails

1

你犯了一个错误的假设，即一旦你改变了一个循环，它仍然保持相同长度的循环。这对于偶数循环来说是不正确的，因此你的算法将无法工作。例如，输入[1,2,3,0]应该得到结果[2,3,0,1]，但你的代码给出了[2,1,0,3]。 - trincot

（@trincot）我没有注意到旋转可能会破坏循环，我已经根据您建议的错误修复实施了修复，因此解决方案不应再有问题。 - Ninetails

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- trincot · Accepted Answer

这是可能的。

输入数组由相同数组中的索引值组成，因此它是一个或多个循环的集合。每个循环可以有1个或多个元素。

最好按照循环进行数组的变异，因为一个循环的改变只需要在该循环中暂时存储一个值，而“下一个”值被复制到“前一个”插槽中，直到整个循环被访问并且可以将临时值放入最后一个插槽。

需要考虑的一件事情是，经过这样的变异后，一个循环的长度可能不会再是相同的。例如，如果一个循环的长度为4，则变异将导致2个具有2个值的循环。更普遍的是，偶数长度的循环将分为两个循环。奇数循环保持其长度，仅改变其顺序。

一旦循环发生变异，算法就不应再“意外地”访问其中任何一个值，并再次将变异应用于该循环。

确保不会发生这种情况的一种方法是，当左到右迭代访问其最右侧元素时，仅对循环应用变异。这是所提出算法的关键。这样，人们可以确信，这个循环中的元素永远不会再次被访问，并且不会再次发生变异。

以下是JavaScript实现。您可以在输入字段中输入数组值。每次更改输入时，算法都会执行：

function arrange(a) {
    function isRightmostOfCycle(i) {
        let j = a[i]
        while (j < i) j = a[j]
        return j == i
    }

    function updateCycle(i) {
        let saved = a[i]
        let k = i
        for (let j = a[i]; j < i; j = a[j]) {
            a[k] = a[j]
            k = j
        }
        a[k] = saved
    }

    for (let i = 0; i < a.length; i++) {
        if (isRightmostOfCycle(i)) updateCycle(i)
    }
    return a
}

// I/O handling
let input = document.querySelector("input")
let output = document.querySelector("pre");
(input.oninput = function () {
    let a = (input.value.match(/\d+/g) || []).map(Number)
    // Check whether input is valid
    let i = a.findIndex((_,i) => !a.includes(i))
    output.textContent = i < 0 ? arrange(a) : "Missing " + i
})();

input { width: 100% }

Array values: <input value="2,0,5,7,6,4,1,8,3"><p>
Result: 
<pre></pre>

检查索引是否表示循环的最右侧元素的时间复杂度为O(n)，因此总时间复杂度为O(n²)。然而，附加的空间复杂度是恒定的。