在常数存储空间中应用置换的算法

Question

我看到这个问题是编程面试书,在这里我简化了问题.

假设你有一个A长度数组n,并且你也有一个P长度排列数组n.您的方法将返回一个数组,其中元素A将以指定索引的顺序出现P.

快速示例:您的方法需要A = [a, b, c, d, e]和P = [4, 3, 2, 0, 1].然后它会回来[e, d, c, a, b].您只能使用常量空间(即您不能分配另一个占用O(n)空间的数组).

想法？

Answer 1

有一个简单的O(n ^ 2)算法,但你可以在O(n)中做到这一点.例如:

A = [a,b,c,d,e]

P = [4,3,2,0,1]

我们可以A用P每个交换所需的正确元素交换每个元素,在每次交换之后,在正确的位置会有一个元素,并以循环方式为每个位置(用^s 指向的交换元素)执行此操作:

[a, b, c, d, e] <- P[0] = 4 != 0 (where a initially was), swap 0 (where a is) with 4
 ^           ^
[e, b, c, d, a] <- P[4] = 1 != 0 (where a initially was), swap 4 (where a is) with 1
    ^        ^
[e, a, c, d, b] <- P[1] = 3 != 0 (where a initially was), swap 1 (where a is) with 3
    ^     ^
[e, d, c, a, b] <- P[3] = 0 == 0 (where a initially was), finish step

在一个圆圈之后,我们发现数组中的下一个元素没有保持在正确的位置,并再次执行此操作.因此,最终您将得到您想要的结果,并且由于每个位置被触摸一个恒定的时间(对于每个位置,最多执行一次操作(交换)),它是O(n)时间.

您可以通过以下方式存储哪个位于其正确位置的信息:

1. 将P中的相应条目设置为-1,这是不可恢复的:在上面的操作之后,P将变为[-1, -1, 2, -1, -1],这表示只有第二个可能不在正确的位置,并且进一步的步骤将确保它在右边定位并终止算法;

2. 将P中的相应条目设置为-n - 1:P变为[-5, -4, 2, -1, -2],可以在O(n)中简单地恢复.

Answer 2

又一个不必要的答案！这个P明确地保留了置换数组，这对我的情况是必要的，但牺牲了成本。此外，这不需要跟踪正确放置的元素。我知道以前的答案提供了O(N)解决方案，所以我想这只是为了娱乐！

我们得到最佳情况复杂度O(N)、最坏情况O(N^2)和平均情况O(NlogN)。对于大型数组（N~10000或更大数组），平均情况本质上是O(N).

这是Java中的核心算法（我的意思是伪代码*咳咳*）

int ind=0;
float temp=0;

for(int i=0; i<(n-1); i++){
  // get next index
  ind = P[i];
  while(ind<i)
    ind = P[ind];

  // swap elements in array
  temp = A[i];
  A[i] = A[ind];
  A[ind] = temp;
}

这是运行算法的示例（类似于以前的答案）：

让 A = [a, b, c, d, e]

和 P = [2, 4, 3, 0, 1]

然后预期 = [c, e, d, a, b]

i=0:  [a, b, c, d, e] // (ind=P[0]=2)>=0 no while loop, swap A[0]<->A[2]
       ^     ^
i=1:  [c, b, a, d, e] // (ind=P[1]=4)>=1 no while loop, swap A[1]<->A[4]
          ^        ^
i=2:  [c, e, a, d, b] // (ind=P[2]=3)>=2 no while loop, swap A[2]<->A[3]
             ^  ^
i=3a: [c, e, d, a, b] // (ind=P[3]=0)<3 uh-oh! enter while loop...
                ^
i=3b: [c, e, d, a, b] // loop iteration: ind<-P[0]. now have (ind=2)<3
       ?        ^
i=3c: [c, e, d, a, b] // loop iteration: ind<-P[2]. now have (ind=3)>=3
             ?  ^
i=3d: [c, e, d, a, b] // good index found. Swap A[3]<->A[3]
                ^
done.

该算法可以在该while循环中为任何索引反弹j<i，最多i在ith迭代期间的大多数时间。在最坏的情况下（我认为！）外for循环的每次迭代都会导致循环中的i额外分配while，因此我们将进行算术级数的事情，这会增加N^2复杂性！运行这个循环并平均循环N所需的“额外”分配的数量while（每个 的许多排列的平均值N，也就是说），强烈建议我，平均情况是O(NlogN).

谢谢！