如何通过索引数组重新排列数组？ [英] How to rearrange an array by indices array?

问题描述

给定一个数组 arr 和一组索引 ind ，我想重新排列 arr 就地以满足给定的索引。例如：

Given an array arr and an array of indices ind, I'd like to rearrange arr in-place to satisfy the given indices. For example:

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） time和 O（1） space， strong>但是变异 ind ：

Here is a possible solution that uses O(n) time and O(1) space, but mutates 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]);
    }
  }
}

什么是最佳解决方案 c c c c c c

What would be the optimal solution if we are limited to O(1) space and mutating ind is not allowed?

编辑：上面的算法是错误的。请参阅此问题。

The algorithm above is wrong. See this question.

推荐答案

这是符号位解决方案。

This is the "sign bit" solution.

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

Given that this is a JavaScript question and the numerical literals specified in the ind array are therefore stored as signed floats, there is a sign bit available in the space used by the input.

该算法根据 ind 数组循环元素，并将元素移动到位回到该循环的第一个元素。然后，它找到下一个循环并重复相同的机制。

This algorithm cycles through the elements according to the ind array and shifts the elements into place until it arrives back to the first element of that cycle. It then finds the next cycle and repeats the same mechanism.

数组在执行期间被修改，但将被恢复到原来的完成算法。在其中一个意见中，你提到这是可以接受的。

The ind array is modified during execution, but will be restored to its original at the completion of the algorithm. In one of the comments you mentioned that this is acceptable.

ind 数组由签名的浮点数组成，尽管它们都是非负数（整数）。该符号位用作该值是否已被处理的指示符。一般来说，这可以被认为是额外的存储（ n 位，即O（n）），但由于存储已经被输入占用，所以不是额外的获取空间。代表周期最左侧成员的 ind 值的符号位不会更改。

The ind array consists of signed floats, even though they are all non-negative (integers). The sign-bit is used as an indicator for whether the value was already processed or not. In general, this could be considered extra storage (n bits, i.e. O(n)), but as the storage is already taken by the input, it is not additional acquired space. The sign bits of the ind values which represent the left-most member of a cycle are not altered.

编辑： strong>我替换了使用〜操作符，因为它不会产生等于或大于 2 ^{31的数字的所需结果} ，而JavaScript应该支持用作数组索引的数字，最多至少 2 ³² - 1 。所以我现在使用相同的 k = -k-1 ，但适用于作为整数使用的整个浮点范围。请注意，作为替代方案，可以使用浮点数小数部分（+/- 0.5）。

I replaced the use of the ~ operator, as it does not produce the desired results for numbers equal or greater than 2³¹, while JavaScript should support numbers to be used as array indices up to at least 2³² - 1. So instead I now use k = -k-1, which is the same, but works for the whole range of floats that is safe for use as integers. Note that as alternative one could use a bit of the float's fractional part (+/- 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）时间：交换每个元素只发生一次，外部循环仅访问每个元素一次。

Although the algorithm has a nested loop, it still runs in O(n) time: the swap happens only once per element, and also the outer loop visits every element only once.

变量声明显示内存使用情况不变，但注意到 ind 数组元素的符号位 - 在空格已经由输入分配的 - 也被使用。

The variable declarations show that the memory usage is constant, but with the remark that the sign bits of the ind array elements -- in space already allocated by the input -- are used as well.

这篇关于如何通过索引数组重新排列数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！