给定目标索引数组，如何就地对数组进行排序？ [英] How to sort an array in-place given an array of target indices?

问题描述

给定目标索引 ind arr 就地进行排序c $ c>？

How would you sort a given array arr in-place given an array of target indices 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"]

我尝试了以下操作算法，但在上面的第二个示例中失败。

I tried the following algorithm, but it fails on the second example above.

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）额外空间？

How would you solve this in O(n) time and O(1) extra space?

您能提供证明算法有效的证据吗？

Could you provide a proof that your algorithm works?

注意：此问题类似于此问题，但此处允许对 ind 进行突变。

Note: This question looks similar to this one, but here mutating ind is allowed.

推荐答案

该算法失败，因为它在列表的索引上只有一个循环。

The algorithm fails because it has only one loop over the indices of your list.

您的算法会发生以下情况：

What happens in your algorithm is this :

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 ，在此示例中不会发生这种情况。

Note how by the first swap, 1 is in position 0 and you will not visit it again unless you swap it with 0, which does not happen in this example.

您的算法遗漏的是遍历索引子周期的内部循环。尝试用替换 if ，而在 rearrange 中替换：

What your algorithm misses is an internal loop that runs through sub-cycles of indexes. Try replacing the if by while in 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循环）。

Note on complexity: although this is a double loop, complexity does not change because at each swap, one element is correctly placed, and each element is read at most twice (once through the cycling, once though the for loop).

关于证明的注意事项：在这里，我不会对此算法做完整的证明，但是我可以给出线索。如果 ind 是一个排列，则所有元素都属于封闭的排列子循环。 while 循环确保您迭代整个循环， for 循环确保您检查所有可能的循环循环。

Note on proof: I will not do a complete proof of this algorithm here, but I can give leads. If ind is a permutation, then all elements belong to closed permutative sub-cycles. The while loop ensures that you're iterating entire cycles, the for loop ensures that you're checking for every possible cycle.

这篇关于给定目标索引数组，如何就地对数组进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！