在恒定内存空间中应用置换的算法 [英] 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

经过一圈后，我们在数组中找到下一个不在正确位置的元素，并再次执行此操作.所以最后你会得到你想要的结果，而且由于每个位置都被触摸了一个恒定的时间(对于每个位置，最多进行一次操作(swap))，所以是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中对应的entry设置为-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中对应的entry设置为-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屋！