在恒定存储空间中应用置换的算法 [英] Algorithm to apply permutation in constant memory space

问题描述

我看到这个问题是一本编程访谈书，在这里我正在简化这个问题.

I saw this question is a programming interview book, here I'm simplifying the question.

假设您有一个长度为n的数组A，并且还具有一个长度为n的排列数组P.您的方法将返回一个数组，其中A的元素将按在P中指定的索引的顺序出现.

Assume you have an array A of length n, and you have a permutation array P of length n as well. Your method will return an array where elements of A will appear in the order with indices specified in P.

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

Quick example: Your method takes A = [a, b, c, d, e] and P = [4, 3, 2, 0, 1]. then it will return [e, d, c, a, b]. You are allowed to use only constant space (i.e. you can't allocate another array, which takes O(n) space).

想法?

推荐答案

有一个简单的O(n ^ 2)算法，但是您可以在O(n)中实现.例如:

There is a trivial O(n^2) algorithm, but you can do this in O(n). E.g.:

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

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

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

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

我们可以将A中的每个元素与P所需的正确元素交换，每次交换之后，在正确的位置将再有一个元素，并以循环方式对每个位置进行此操作(交换指向^ s的元素):

We can swap each element in A with the right element required by P, after each swap, there will be one more element in the right position, and do this in a circular fashion for each of the positions (swap elements pointed with ^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).

After one circle, we find the next element in the array that does not stay in the right position, and do this again. So in the end you will get the result you want, and since each position is touched a constant time (for each position, at most one operation (swap) is performed), it is O(n) time.

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

You can stored the information of which one is in its right place by:

1. 将P中的相应条目设置为-1，这是不可恢复的:完成上述操作后，P将变为[-1, -1, 2, -1, -1]，这表示只有第二个可能不在正确的位置，而另一个步骤将确保其位置正确并终止算法；

1. set the corresponding entry in P to -1, which is unrecoverable: after the operations above, P will become [-1, -1, 2, -1, -1], which denotes that only the second one might be not in the right position, and a further step will make sure it is in the right position and terminates the algorithm;

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

set the corresponding entry in P to -n - 1: P becomes [-5, -4, 2, -1, -2], which can be recovered in O(n) trivially.

这篇关于在恒定存储空间中应用置换的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！