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

Question

在给定目标索引数组 ind 的情况下，您将如何对给定数组 arr in-place 进行排序？

例如:

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 中将 if 替换为 while:

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 循环确保您检查每个可能的循环。