如何在給定目標索引數組的情況下對數組進行排序？

Question

如何給定一個給定數組arrin-place給定一組目標指數ind？

例如：

var arr = ["A", "B", "C", "D", "E", "F"]; 
var ind = [ 4, 0, 5, 2, 1, 3 ]; 

rearrange(arr, ind); 

console.log(arr); // => ["B", "E", "D", "F", "A", "C"] 

arr = ["A", "B", "C", "D"]; 
ind = [ 2, 3, 1, 0 ]; 

rearrange(arr, ind); 

console.log(arr); // => ["D", "C", "A", "B"] 

我嘗試以下的算法，但它上面的第二示例失敗。

function swap(arr, i, k) { 
    var temp = arr[i]; 
    arr[i] = arr[k]; 
    arr[k] = temp; 
} 

function rearrange(arr, ind) { 
    for (var i = 0, len = arr.length; i < len; i++) { 
    if (ind[i] !== i) { 
     swap(arr, i, ind[i]); 
     swap(ind, i, ind[i]); 
    } 
    } 
} 

如何在O（n）時間和O（1）額外空間解決這個問題？

你能提供一個證明你的算法有效嗎？

---

注：這個問題類似於this one，但這裏變異ind是允許的。

Answer 1

算法失敗，因爲它只有一個在你的列表的索引循環。

在你的算法會發生什麼事是這樣的：

i=0 -> ["A", "B", "C", "D"] , [ 2, 3, 1, 0 ] 
i=1 -> ["C", "B", "A", "D"] , [ 1, 3, 2, 0 ] 
i=2 -> ["C", "D", "A", "B"] , [ 1, 0, 2, 3 ] 
i=3 -> ["C", "D", "A", "B"] , [ 1, 0, 2, 3 ] 

說明如何通過第一個交換，1是0位置，除非你用0掉它，這不會發生，你不會再次訪問它這個例子。

你的算法錯過了一個內部循環，它貫穿索引的子循環。嘗試在rearrange由while更換if：

function rearrange(arr, ind) { 
    for (var i = 0, len = arr.length; i < len; i++) { 
     while (ind[i] !== i) { 
     swap(arr, i, ind[i]); 
     swap(ind, i, ind[i]); 
     } 
    } 
} 

注複雜性：雖然這是一個雙循環，複雜性並不因爲每個交換改變，一個元件正確放置，其各要素閱讀最多兩次（一次循環，一次循環）。

關於證明的注意事項：我不會在這裏做這個算法的完整證明，但我可以提供線索。如果ind是置換，則所有元素都屬於閉合置換子循環。 while循環確保您迭代整個循環，for循環可確保您檢查每個可能的循環。

Answer 2

如何在O（n）時間解決這個問題？

只需使用臨時陣列和迭代陣列的兩倍，您可以將其降低到O(n)

function rearrange(arr, ind) 
{ 
    var temp = [], len = arr.length; 
    //first re-arrange in a new array 
    for(var counter = 0; counter < len; counter++) 
    { 
    temp[ind[counter]] = arr[counter]; 
    } 
    //copy the values as per new indices from temp 
    for(var counter = 0; counter < len; counter++) 
    { 
    arr[counter] = temp[counter]; 
    } 
} 

Answer 3

如果您滿意這樣做，用更少的複雜性的方法，那麼有一個：

• 請長度等於arr長度並與空對象的新數組
• splice通過ind[i]索引中的新的數組，取出1個對象，以及與arr[i]
• 更換用新的

window.onload = function() { 
 
    
 
    'use strict'; 
 
\t 
 
\t var arr = ["A", "B", "C", "D", "E", "F"]; 
 
\t var ind = [ 4, 0, 3, 2, 1, 5 ]; 
 
\t var temp = []; 
 

 
\t for (var i = 0; i < arr.length; i++) { 
 
\t  temp[i] = ''; 
 
\t } 
 

 
\t for (var v = 0; v < arr.length; v++) { 
 
\t  temp.splice(ind[v], 1, arr[v]); 
 
\t } 
 
\t 
 
\t arr = temp; 
 
\t console.log(arr); 
 
};

Answer 4

我均衡舊陣列（arr）建議您將結果返回到新陣列中

function createArray(arr, ind) { 
     var result = []; 
     for (var i = 0, len = arr.length; i < len; i++) { 
      result.push(arr[ind[i]]); 
     } 
     return result; 
    } 

這是O（n）的時間

var arr = ["A", "B", "C", "D", "E", "F"]; 
var ind = [4, 0, 5, 2, 1, 3]; 
console.log(createArray(arr,ind)) 

Answer 5

上有類似的問題很多討論In-place array reordering?

不同的是，在最初的問題ind[i]爲元件arr[i]所需索引，而在類似的問題i爲元件arr[ind[i]]

再回到原來的算法所需的索引，一個工作替代可以是

function swap(arr, i, k) { 
    var temp = arr[i]; 
    arr[i] = arr[k]; 
    arr[k] = temp; 
} 

function rearrange(arr, ind) { 
    for (var i = 0, len = arr.length; i < len; i++) { 
    if (ind[i] !== i) { 
     swap(arr, i, ind[i]); 
     swap(ind, i, ind[i]); 
     if (ind[i] < i) { 
     i = ind[i]-1; 
     } 
    } 
    } 
} 

它仍然O(1)空間，但它使多餘的檢查，而且可能比O(n)

Answer 6

我建議換，直到達到同樣的指標，然後採取下一步的外指數更復雜。

function swap(arr, i, k) { 
 
    var temp = arr[i]; 
 
    arr[i] = arr[k]; 
 
    arr[k] = temp; 
 
} 
 

 
function rearrange(arr, ind) { 
 
    var i = arr.length; 
 
    while (i--) { 
 
     while (ind[i] !== i) { 
 
      swap(arr, i, ind[i]); 
 
      swap(ind, i, ind[i]); 
 
     } 
 
    } 
 
} 
 

 
var arr = ["A", "B", "C", "D", "E", "F"]; 
 
var ind = [ 4, 0, 5, 2, 1, 3 ]; 
 

 
rearrange(arr, ind); 
 
console.log(arr); // => ["B", "E", "D", "F", "A", "C"] 
 

 
arr = ["A", "B", "C", "D"]; 
 
ind = [ 2, 3, 1, 0 ]; 
 

 
rearrange(arr, ind); 
 
console.log(arr); // => ["D", "C", "A", "B"];

Answer 7

「旋轉」循環而不是使用交換有點快。 C的例子：

// reorder A in place according to sorted indices in I 
    // tA is temp value for A 
    for(i = 0; i < n; i++){ 
     if(i != I[i]){ 
      tA = A[i]; 
      k = i; 
      while(i != (j = I[k])){ 
       A[k] = A[j]; 
       I[k] = k; 
       k = j; 
      } 
      A[k] = tA; 
      I[k] = k; 
     } 
    }