如何通过索引数组重新排列数组？

Question

给定一个数组arr和一个索引数组ind,我想arr 在原地重新排列以满足给定的索引.例如:

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"]

这是一个使用O(n)时间和O(1)空间的可能解决方案,但是变异ind:

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(1)ind

---

编辑:上面的算法是错误的.看到这个问题.

Answer 1

这是"符号位"解决方案.

鉴于这是一个JavaScript问题,因此ind数组中指定的数字文字存储为有符号浮点数,输入使用的空间中有一个符号位.

该算法根据ind数组循环遍历元素,并将元素移位到位,直到它返回到该循环的第一个元素.然后它找到下一个循环并重复相同的机制.

该IND阵列执行期间修改,但将在该算法的完成时恢复到原来的.在你提到的其中一条评论中,这是可以接受的.

该IND阵列由签署花车,即使他们都是非负(整数).符号位用作指示值是否已经处理.通常,这可以被认为是额外的存储(n位,即O(n)),但是由于存储已经被输入占用,所以它不是额外的获取空间.表示循环最左边成员的ind值的符号位不会改变.

编辑:我替换了~运算符的使用,因为它不会产生等于或大于2 ^31的数字的期望结果,而JavaScript应该支持数字作为数组索引使用至少2 ³² - 1.所以我现在使用k = -k-1,它是相同的,但适用于整个范围的浮点数,可以安全地用作整数.请注意,作为替代,可以使用浮点的小数部分(+/- 0.5).

这是代码:

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

rearrange(arr, ind);

console.log('arr: ' + arr);
console.log('ind: ' + ind);

function rearrange(arr, ind) {
    var i, j, buf, temp;
    
    for (j = 0; j < ind.length; j++) {
        if (ind[j] >= 0) { // Found a cycle to resolve
            i = ind[j];
            buf = arr[j];
            while (i !== j) { // Not yet back at start of cycle
                // Swap buffer with element content
                temp = buf;
                buf = arr[i];
                arr[i] = temp;
                // Invert bits, making it negative, to mark as visited
                ind[i] = -ind[i]-1; 
                // Visit next element in cycle
                i = -ind[i]-1;
            }
            // dump buffer into final (=first) element of cycle
            arr[j] = buf;
        } else {
            ind[j] = -ind[j]-1; // restore
        }
    }
}

尽管该算法具有嵌套循环,但它仍然在O(n)时间内运行:每个元素只发生一次交换,外部循环也只访问每个元素一次.

变量声明显示内存使用量是常量,但是注意到ind数组元素的符号位- 在已经由输入分配的空间中 - 也被使用.