logo标签列表

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

javascriptarraysalgorithmsortingdata-structures
21

给定一个数组 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，那么什么是最优解决方案？

编辑：上面的算法是错误的。请查看this question。

3
考虑到你的限制，你确定是否存在解决方案？ - Nick Zuber
1
如果我说我在JavaScript中使用了一个具有最大大小的数组，那么这个解决方案将是O(1)，因为它是常数且与n无关 :) - Nuri Tasdemir
@Misha Moroshko，您能否请检查一下我的答案。https://dev59.com/IloU5IYBdhLWcg3wcmq8#37466714 - Redu
2
在我看来，这个问题似乎可以通过使用由ind中的索引给出的字母"A"..."Z"的顺序对arr进行排序来解决。因此，您正在询问是否可能使用恒定空间的线性时间排序数组。最好的线性时间排序算法（基数排序、桶排序、计数排序）无法实现这一点，因此我怀疑没有一个已知的最优解决方案适用于您的问题。 - James Lawson
2
@JamesLawson，我不同意这是一个（经典的）排序算法，因为每个元素的最终位置已经作为输入给出，而即使对于基数类排序算法也不是这种情况。我认为一些给出的答案代表了执行重新排列的最佳解决方案。 - trincot
显示剩余8条评论
9个回答
9
这是“符号位”解决方案。
考虑到这是一个JavaScript问题，并且在“ind”数组中指定的数字文字因此存储为有符号浮点数，因此输入使用的空间中有一个符号位。
该算法根据“ind”数组循环遍历元素并将元素移位到其位置，直到到达该周期的第一个元素。然后它找到下一个周期并重复相同的机制。
“ind”数组在执行过程中被修改，但将在算法完成时恢复原样，你在其中一条评论中提到这是可以接受的。
“ind”数组由带符号浮点数组成，即使它们都是非负整数。符号位用作指示器，表示值是否已处理。通常情况下，这可以视为额外存储（n位，即O（n）），但由于存储已被输入占用，因此不是额外获取的空间。表示循环左侧成员的“ind”值的符号位不会更改。
编辑：我替换了对“〜”运算符的使用，因为它不会产生大于等于2 ^ 31的数字的所需结果，而JavaScript应支持使用数字作为数组索引至少达到2 ^ 32-1。因此，我现在使用k = -k-1，它相同，但适用于安全用作整数的整个float范围。请注意，作为替代，可以使用浮点数的小数部分的一位（+/- 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数组元素的符号位也被使用。

仅从外观上看，这对我来说不像是O(n) - 如果我错了请纠正我。 - Nick Zuber
我的辩解是它的时间复杂度为O(n)，具体解释请看代码片段下面的文字。 - trincot
1
我接近于相同的解决方案：你无法在某种方式下“保存”先前访问过的元素，就解决不了这个问题。我认为，在给定的限制条件下，这是最好的方法。 - Pablo Lozano
2
我对此有两种不同的看法：一方面，问题参数涉及JavaScript数组，通常是32/64位带符号浮点数，并且数组索引传统上不依赖于符号，因此使用它，虽然在理论上是O(n)空间，但并不会增加额外的空间；另一方面，在JavaScript中，您也可以这样做array[-3] = somevalue，如果ind包括负值，则可能会使您的算法难以使用。 - גלעד ברקן
1
@le_m，尽管 +0.5 版本可行，但我回到了使用符号位的原始想法，因为我觉得它更优雅。我只是用 -ind[i]-1 代替了 ~ind[i]，在更高的安全整数范围内按需工作。 - trincot
显示剩余17条评论
4

索引数组定义了一个排列。每个排列由循环组成。我们可以通过沿着每个循环并逐步替换数组元素来重新排列给定的数组。

唯一的问题在于要确保只跟随每个周期一次。一种可能的方法是按顺序处理数组元素，并为每个元素检查通过该元素的循环。如果这样的循环至少与一个索引较小的元素接触，则沿着该循环的元素已经被置换。否则，我们将遵循该周期并重新排序元素。

function rearrange(values, indexes) {
    main_loop:
    for (var start = 0, len = indexes.length; start < len; start++) {
        var next = indexes[start];
        for (; next != start; next = indexes[next])
            if (next < start) continue main_loop;

        next = start;
        var tmp = values[start];
        do {
            next = indexes[next];
            tmp = [values[next], values[next] = tmp][0]; // swap
        } while (next != start);
    }
    return values;
}

这个算法只会覆盖给定数组的每个元素一次，不会改变索引数组（即使是暂时性的）。它的最坏情况复杂度是O(n2)。但对于随机排列，其预期复杂度为O(n log n)（如相关答案的评论所述）。
这个算法可以进行一些优化。最明显的优化是使用一个短的位集来保持有关当前位置之前几个索引的信息（它们是否已经被处理过）。使用单个32或64位字来实现此位集不应违反O(1)空间要求。这种优化将带来小但明显的速度提升。虽然它并不改变最坏情况和预期渐近复杂度。
为了更进一步地优化，我们可以暂时使用索引数组。如果此数组的元素至少有一个备用位，我们可以使用它来维护一个位集，允许我们跟踪所有已处理的元素，从而得到一个简单的线性时间算法。但我认为这不能被视为O(1)空间算法。因此，我假设索引数组没有备用位。
尽管如此，索引数组仍然可以为我们提供一些空间（比单个字大得多）用于前瞻位集。因为这个数组定义了一个排列，它包含的信息比相同大小的任意数组要少得多。Stirling近似公式对于ln(n!)给出了n ln n位的信息，而数组可以存储n log n位。自然对数和二进制对数之间的差异使我们获得了约30%的潜在自由空间。此外，如果数组的大小不是2的幂，或者换句话说，高阶位仅部分使用，则我们可以提取最多1/64 = 1.5%或1/32 = 3%的自由空间。（而这1.5%可能比保证的30%更有价值）。
这个想法是将所有索引压缩到当前位置的左侧（因为它们从未被算法使用），使用压缩数据和当前位置之间的可用自由空间的一部分来存储前瞻位集（以提高主算法的性能），使用其他自由空间的一部分来提高压缩算法本身的性能（否则我们只需要用平方时间进行压缩），最后将所有索引解压回原始形式。
为了压缩索引，我们可以使用阶乘数系统：扫描索引数组以找到有多少个索引小于当前索引，将结果放入压缩流中，并使用可用的自由空间同时处理几个值。
这种方法的缺点是大部分的自由空间是在算法到达数组末尾时产生的，而这个空间在我们处于开头时是最需要的。因此，最坏情况下的复杂度可能只比O(n2)略低。如果不是这个简单的技巧：在算法足够便宜时使用原始算法（不进行压缩），然后切换到“压缩”变体，那么这也可能增加预期复杂度。
如果数组长度不是2的幂（且我们有部分未使用的高位比特），我们可以忽略索引数组包含排列的事实，并将所有索引打包，就好像在基为n的数字系统中一样。这样可以大大减少最坏情况渐进复杂度，并加速“平均情况”下的算法。
+1用于指出相关答案。不确定是否适合作为重复目标。 - Bergi
@Redu：它在您的数据上给出[K，M，U，H，B，W，L，O，C，D，I，E，N，S，V，P，X，A，Q，F，Y，Z，R，T，J，G]。看起来完全正确。(http://ideone.com/bBZzWx) - Evgeny Kluev
@Evgeny Kluev 对不起，你的代码没问题。是我的测试有误。 - Redu
1

这个提案使用了Evgeny Kluev的answer。

我为了更快的处理，做了一个扩展，如果所有元素都已经处理完毕，但索引还没有到达零，则会使用一个附加变量count，它会对每个替换的元素进行倒计数。这用于在所有元素处于正确位置时离开主循环（count = 0）。

这对于类似第一个例子中的环非常有帮助。

["A", "B", "C", "D", "E", "F"]
[ 4,   0,   5,   2,   1,   3 ]

index 5: 3 -> 2 -> 5 -> 3
index 4: 1 -> 0 -> 4 -> 1

最开始，两个环都重新排列了两个循环，而每个环都有3个元素，但此时count为零。这导致外部while循环出现短路。

function rearrange(values, indices) {
    var count = indices.length, index = count, next;

    main: while (count && index--) {
        next = index;
        do {
            next = indices[next];
            if (next > index) continue main;
        } while (next !== index)
        do {
            next = indices[next];
            count--;
            values[index] = [values[next], values[next] = values[index]][0];
        } while (next !== index)
    }
}

function go(values, indices) {
    rearrange(values, indices);
    console.log(values);
}

go(["A", "B", "C", "D", "E", "F"], [4, 0, 5, 2, 1, 3]);
go(["A", "B", "C", "D", "E", "F"], [1, 2, 0, 4, 5, 3]);
go(["A", "B", "C", "D", "E", "F"], [5, 0, 1, 2, 3, 4]);
go(["A", "B", "C", "D", "E", "F"], [0, 1, 3, 2, 4, 5]);

0

此答案已更新以满足 OP 的条件

在这个答案中，没有临时数组，并且 ind 数组不会被重新排序或排序。所有替换操作都在单次遍历中完成。 getItemIndex 函数仅接收 ind 数组的浅部分进行处理。这只是通过利用 ind 数组中隐藏的所有信息来完成的。

重要的是要理解，ind 数组为我们保留了所有历史记录。

通过检查 ind 数组，我们可以获得以下信息。

  1. 通过查看项目，我们找到相应项目在 arr 数组中的索引映射。
  2. 每个项目的索引告诉我们之前做了多少次交换。我们得到历史记录。
  3. 每个项目的索引还告诉我们是否有与当前索引位置相关的先前交换，先前元素去哪里了。我们可以像 ind.indexOf(i) 这样做；无论如何，这是代码；

我添加了一些函数，例如 Array.prototype.swap()，以使代码易于解释。以下是代码。

Array.prototype.swap = function(i,j){
  [this[i],this[j]] = [this[j],this[i]];
  return this;
};

function getItemIndex(a,i){
  var f = a.indexOf(i);
  return f !=-1 ? getItemIndex(a,f) : i;
}

function sort(arr,ind){
  ind.forEach((n,i,x) => x.indexOf(i) > i ? arr.swap(i,x[i]) // item has not changed before so we can swap 
                                          : arr.swap(getItemIndex(ind.slice(0,i),i),x[i])); // item has gone to somwhere in previous swaps get it's index and swap
  return arr;
}

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


console.log(sort(arr,ind),ind);

好的，这段代码的最终版本如下。它非常简化，并包含了一个带有26个字母的测试用例。每次运行时，您将获得一个不同的纯随机唯一索引映射。

Array.prototype.swap = function(i,j){
  i !=j && ([this[i],this[j]] = [this[j],this[i]]);
  return this;
};

Array.prototype.shuffle = function(){
  var i = this.length,
      j;
  while (i > 1) {
    j = ~~(Math.random()*i--);
    [this[i],this[j]] = [this[j],this[i]];
  }
return this;
};

var   arr = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"],
      ind = (new Array(arr.length)).fill("").map((e,i) => e = i).shuffle();
console.log(JSON.stringify(arr));
console.log(JSON.stringify(ind));

function getItemIndex(a,i,j){
  var f = a.indexOf(i);
  return f < j ? getItemIndex(a,f,j) : i;
}

function sort(arr,ind){
  ind.forEach((n,i,x) => arr.swap(getItemIndex(ind,i,i),n));
  return arr;
}
console.log(JSON.stringify(sort(arr,ind)));
console.log(JSON.stringify(ind));

所以根据Trincot的评论，这里使用迭代的getItemIndex()函数。

Array.prototype.swap = function(i,j){
  i !=j && ([this[i],this[j]] = [this[j],this[i]]);
  return this;
};

Array.prototype.shuffle = function(){
  var i = this.length,
      j;
  while (i > 1) {
    j = ~~(Math.random()*i--);
    [this[i],this[j]] = [this[j],this[i]];
  }
return this;
};

var   arr = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"],
      ind = (new Array(arr.length)).fill("").map((e,i) => e = i).shuffle();
console.log(JSON.stringify(arr));
console.log(JSON.stringify(ind));

function getItemIndex(a,i){
  var f = a.indexOf(i),
      j;
  if (f >= i) return i; // this element hasn't been moved before.
  while (f < i) {       // this element has been swapped so get this elements current index
   j = f;
   f = a.indexOf(f);
  }
  return j;
}

function sort(arr,ind){
  ind.forEach((n,i,x) => arr.swap(getItemIndex(ind,i),n));
  return arr;
}
console.log(JSON.stringify(sort(arr,ind)));
console.log(JSON.stringify(ind));

我收到一个错误：赋值语句左侧无效。 - Nina Scholz
请提供需要翻译的英文内容。 - Nina Scholz
@FizzyTea 好的，ind 保持不变。没有临时数组，也没有对 ind 数组进行任何修改，只需使用单个 forEach 循环来进行交换。 - Redu
1
请注意，这需要O(n²)的时间。 - Bergi
1
我认为你不能使用slice，因为它会分配数组长度的内存空间。此外，在getItemIndex中递归调用会消耗堆栈空间，最坏情况下可能是O(n)。 - trincot
显示剩余11条评论
0
var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];

function rearrange(arr, ind){
  var map = [];
  for (var i = 0; i < arr.length; i++)   map[ind[i]] = arr[i];
  for (var i = 0; i < arr.length; i++)   arr[i] = map[i];
}

rearrange(arr, ind);

console.log(arr);

这个方法可以工作，但是由于我不是一个聪明的开发者，我认为它可能不是最快的算法。

使用 O(n) 空间。 - trincot
我承认不知道 O(n) 的含义是什么。 - kevin ternet
1
这实际上意味着该算法分配了额外的内存（map），其大小与输入数组的长度成线性关系。问题在于要在恒定大小的内存中执行它（O（1）），无论输入数组有多大。 - trincot
@tricot，如果我使用 Array.prototype.map() 而不是 for 循环，它是否总是 **O(n)**？ - kevin ternet
Array.prototype.map 返回一个新创建的数组，因此如果将其应用于其中一个输入数组，则仍会分配 O(n) 的额外空间。要使其成为 **O(1)**，您需要找到一种只使用有限数量的简单变量（而不是数组）的方法，以便您不使用随着输入变大而变得更大的空间，而是保持不变，无论输入数组有多大。 - trincot
0
以下是针对仅有一个循环的情况的部分解决方案，即：
var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 2, 5, 0, 1, 3];

function rearrange( i, arr, ind, temp ){
    if( temp ){
        if( arr[ind[i]] ){
            var temp2 = arr[ind[i]];
            arr[ind[i]] = temp;
            rearrange( ind[i], arr, ind, temp2 );
        }
        else{                                           // cycle
            arr[ind[i]] = temp;
            // var unvisited_index = ...;
            // if( unvisited_index ) rearrange( unvisited_index, arr, ind, "" );
        }
    }
    else{
        if( i == ind[i] ){
            if( i < arr.length ) rearrange( i + 1, arr, ind, temp );    
        }
        else{
            temp = arr[ind[i]];
            arr[ind[i]]=arr[i];
            arr[i] = "";
            i = ind[i];
            rearrange(i, arr, ind, temp );
        }
    }
}

rearrange( 0, arr, ind, "" );

为了使这个解决方案适用于一般情况，我们需要找到所有唯一循环的总数以及每个循环中的一个索引。
对于OP示例：
var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];

有2个独特的循环：

4 -> 1 -> 0 -> 4
5 -> 3 -> 2 -> 5

如果有人运行

rearrange( 0, arr, ind, "" );
rearrange( 5, arr, ind, "" );

对于 OP 问题，(他/她) 将获得理想的输出。

对于任何给定的数组，您如何知道要调用哪些函数来调用rearrange以获得最终结果？ - trincot
@trincot，就像我说的，我不知道如何有效地解决它。这是一个特定情况下仅有一个循环的部分解决方案。对于任何给定的数组，它可以在O(1)空间内完成，但你需要迭代除第一个索引以外的每个索引，并对已发现的所有循环应用循环检测算法（例如Floyd或Brent）。显然，这将导致运行时间变慢。 - lllllllllll
0

我不确定时间，但是map函数似乎可以完成所需的功能。这是一个选项，但由于我不知道.map的内部工作原理，所以我不能确定这是否是您要寻找的。

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

arr = ind.map(function(value)
{ return arr[value]; });

另一种不使用 map 函数的解决方案可能看起来像这样：

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

var temp = [];

for (var i = 0, ind_length = ind.length; i < ind_length; i++) 
{ 
    var set_index = ind[i];
    temp.push(arr[set_index]); 
    delete arr[set_index]; 
}

arr = temp;

这种方法通过使用删除选项并保持索引不变来很好地利用了空间。由于只执行一次循环，我想执行速度相当快。由于命令非常基本和简单，因此这应该是一个可行的解决方案。虽然它不完全符合要求（即不使用额外的空间进行交换），但它非常接近。我是第一次回答这样的问题，请提出建设性的批评。

数组元素的移动好像是根据 ind[i] 的值来确定 arr[i] 的值应该从哪里被 取出，但问题是不同的：ind[i] 的值表示 arr[i] 的值应该被移动到哪里。检查代码生成的输出并将其与问题中所需的输出进行比较。 - trincot
此外，这个解决方案不会 原地修改 arr。它实际上创建了一个新的数组。如果您将此算法创建为函数（最终您可能会想要这样做），并将 arr 作为参数传递，则第一个解决方案不会改变 arr 中的任何内容，而第二个解决方案将删除 arr 中的所有元素。 - trincot
@trincot 我完全误解了请求...天啊。我搞砸了。我知道这不会进行原地修改，但那时候这是我能想到的最好的方法。感谢您的反馈~好观点。 - Robert McMahan
0

试试这个：

var result = new Array(5);
for (int i = 0; i < result.length; i++) {
    result[i] = arr[ind[i]];
}
console.log(arr);
代码应该是通用的，所以new Array(5)最好只是[]或new Array(arr.length)。但是通过创建这个数组，你使用了**O(n)空间，而问题是要使用O(1)**空间。 - trincot
-2

我正在使用ind作为索引，按照它们自己的顺序。

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];
var obj = {}
for(var i=0;i<arr.length;i++)
    obj[ind[i]]=arr[i];
console.log(obj);

工作的Fiddle

obj 使用 O(n) 的空间。 - trincot
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接