重新排列数组，这样ARR [I]变成编曲[ARR [I]与O（1）额外的空间 [英] Rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space

问题描述

的任务是重新排列数组，这样改编[I] 变成改编[ARR [I]] 与 O（1）额外的空间。

例如：

  2 1 3 5 4 0
 

变成了：

  3 1 5 0 4 2
 

我能想到的 O（N²）解决方案。一个 O（N）溶液presented的这里：

  

  
1. 增加每个数组元素改编[I] 按（ARR [改编[I]％N）* N 。
  
2. 按 N 。
分割的每一个元素   

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

任何人都可以想出在此有所改善？

解决方案

如果该数组中的值都是正（或所有负），以避免溢出单程可以是运行排列周期，并使用整数符号到标志访问索引。 （可替代地，如果阵列长度小于2 ^（比特数为一个数组元素 - 1），而不是使用符号，我们可能会改变的所有值中的一个位到左侧，并使用所述第一位来标记访问过的索引。）在运行的时间比你所要求的改进算法该算法的结果均不迭代和原始数组值较少的修改。

的jsfiddle： http://jsfiddle.net/alhambra1/ar6X6/

JavaScript的code：

 功能重新排列（ARR）{
    VAR走访= 0，TMP，索引，zeroTo

    函数周期（startIx）{
        TMP = {启动：startIx，值：常用3 [startIx]}
        指数= {来自：常用3 [startIx]，以：startIx}

        而（indexes.from！= tmp.start）{
            如果（ARR [indexes.from] == 0）
                zeroTo = indexes.to
            如果（indexes.to ==访问）{
                参观++
                ARR [indexes.to] = ARR [indexes.from]
            } 其他 {
                ARR [indexes.to] = -arr [indexes.from]
            }
            indexes.to = indexes.from
            如果（indexes.from！= tmp.start）
                indexes.from = ARR [indexes.from]
        }

        如果（indexes.to ==访问）{
            参观++
            ARR [indexes.to] = tmp.value
        } 其他 {
            ARR [indexes.to] = -tmp.value
        }
    }

    而（参观＆LT; arr.length  -  1）{
        周期（访问）

        而（ARR [拜访]℃的||参观== zeroTo）{
            ARR [走访] = -arr [访问]
            参观++
        }
    }

    回报ARR
}
 

The task is to rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space.

Example:

2 1 3 5 4 0 

becomes:

3 1 5 0 4 2

I can think of an O(n²) solution. An O(n) solution was presented here:

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

But this is very limited as it will cause buffer overflow.

Can anyone come up with an improvement upon this?

解决方案

If the values in the array are all positive (or all negative), one way to avoid overflow could be to run the permutation cycles and use the integer sign to mark visited indexes. (Alternatively, if the array length is smaller than 2^(number of bits for one array element - 1), rather than use the sign, we could shift all the values one bit to the left and use the first bit to mark visited indexes.) This algorithm results in both less iterations and less modifications of the original array values during run-time than the algorithm you are asking to improve.

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

JavaScript code:

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
}

这篇关于重新排列数组，这样ARR [I]变成编曲[ARR [I]与O（1）额外的空间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！