如何在给定目标索引数组的情况下对数组进行排序？

Question

arr 在给定目标索引数组的情况下,如何对给定数组进行排序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)额外空间中解决这个问题？

你能提供一个证明你的算法有效吗？

---

注意:这个问题类似于这一个,但这里变异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,这在此示例中不会发生.

您的算法遗漏的是一个内部循环,它贯穿索引的子循环.尝试更换if用while在rearrange:

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]);
      }
   }
}

关于复杂性的注意事项:虽然这是一个双循环,但复杂性不会改变,因为在每次交换时,一个元素被正确放置,并且每个元素最多被读取两次(一次通过循环,一次通过for循环).

关于证明的注意事项:我不会在这里完整地证明这个算法,但我可以给出引导.如果ind是置换,则所有元素都属于闭合的置换子循环.该while循环确保你遍历整个周期的for循环确保你检查每一个可能的周期.