arrays - 重新排列一个数组，使 arr[i] 变成 arr[arr[i]] 并增加 O(1) 的额外空间

Question

任务是重新排列一个数组，使 arr[i] 变成 arr[arr[i]]，复杂度为 O(1)额外的空间。

例子:

2 1 3 5 4 0 

变成:

3 1 5 0 4 2

我可以想到一个O(n²) 的解决方案。提出了一个 O(n) 解决方案 here :

1. Increase every array element arr[i] by (arr[arr[i]] % n)*n.
2. Divide every element by n.

但这非常有限，因为它会导致缓冲区溢出。

谁能对此提出改进意见？

Answer 1

如果数组中的值全部为正(或全部为负)，避免溢出的一种方法是运行置换循环并使用整数符号标记已访问的索引。 (或者，如果数组长度小于 2^(一个数组元素的位数 - 1)，而不是使用符号，我们可以将所有值向左移动一位并使用第一位标记访问索引.) 与您要求改进的算法相比，该算法在运行时对原始数组值的迭代和修改都更少。

JSFiddle:http://jsfiddle.net/alhambra1/ar6X6/

JavaScript 代码:

function rearrange(arr){
    var visited = 0,tmp,indexes,zeroTo

    function cycle(startIx){
        tmp = {start: startIx, value: arr[startIx]}
        indexes = {from: arr[startIx], to: startIx}

        while (indexes.from != tmp.start){
            if (arr[indexes.from] == 0)
                zeroTo = indexes.to
            if (indexes.to == visited){
                visited++
                arr[indexes.to] = arr[indexes.from]
            } else {
                arr[indexes.to] = -arr[indexes.from]
            }
            indexes.to = indexes.from
            if (indexes.from != tmp.start)
                indexes.from = arr[indexes.from]
        }

        if (indexes.to == visited){
            visited++
            arr[indexes.to] = tmp.value
        } else {
            arr[indexes.to] = -tmp.value
        }
    }

    while (visited < arr.length - 1){
        cycle(visited)

        while (arr[visited] < 0 || visited == zeroTo){
            arr[visited] = -arr[visited]
            visited++
        }
    }

    return arr
}