重新排列陣列，使arr [i]變爲帶有O（1）額外空間的arr [arr [i]]

Question

任務是重新排列陣列，以使arr[i]變爲arr[arr[i]]，並帶有O(1)額外空間。

實施例：

2 1 3 5 4 0 

變爲：

3 1 5 0 4 2 

我能想到的O(n²)溶液。通過(arr[arr[i]] % n)*n

1. 增加每個數組元素arr[i]：一個O(n)溶液呈現here。
2. 將每個元素除以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 
}