我看到这个问题是一本编程面试书，这里我简化了这个问题。
假设您有一个A长度数组，并且您也有一个长度n排列数组。您的方法将返回一个数组，其中的元素将按.PnAP
快速示例：您的方法采用A = [a, b, c, d, e]and P = [4, 3, 2, 0, 1]。然后它会返回[e, d, c, a, b]。您只能使用常量空间（即您不能分配另一个占用O(n)空间的数组）。
想法？
问问题
8354 次
9 回答
12
There is a trivial O(n^2) algorithm, but you can do this in O(n). E.g.:
A = [a, b, c, d, e]
P = [4, 3, 2, 0, 1]
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
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:
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;set the corresponding entry in P to
-n - 1: P becomes[-5, -4, 2, -1, -2], which can be recovered in O(n) trivially.
于 2013-05-11T20:32:23.857 回答
7
又是一个不必要的答案！这一个明确地保留了排列数组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).
谢谢！
于 2017-01-04T20:37:05.513 回答
2
最简单的情况是当一个元素只有一次交换到目标索引时。例如： array=abcd perm =1032。你只需要两个直接交换：ab 交换，cd 交换
对于其他情况，我们需要不断交换，直到元素到达其最终目的地。例如：abcd, 3021 从第一个元素开始，我们交换 a 和 d。我们在perm[perm[0]]检查 a 的目的地是否为 0 。它不是，所以我们在array[perm[perm[0]]]处将 a 与 elem 交换，即 b。我们再次检查 a 是否已在perm[perm[perm[0]]]到达目的地，是的。所以我们停下来。
我们对每个数组索引重复此操作。每个项目只移动一次，所以它是 O(N) 和 O(1) 存储。
def permute(array, perm):
for i in range(len(array)):
elem, p = array[i], perm[i]
while( p != i ):
elem, array[p] = array[p], elem
elem = array[p]
p = perm[p]
return array
于 2019-12-29T01:05:43.680 回答
1
@RinRisson给出了迄今为止唯一完全正确的答案！其他所有答案都需要额外的存储空间——O(n) 堆栈空间，或者假设置换 P 被方便地存储在 O(n) 未使用但可变符号位附近，或其他任何东西。
这是用 C++ 编写的 RinRisson 的正确答案。这通过了我对其进行的所有测试，包括对长度为 0 到 11 的所有可能排列的详尽测试。
请注意，您甚至不需要实现排列；我们可以将其视为完全黑盒功能OldIndex -> NewIndex：
template<class RandomIt, class F>
void permute(RandomIt first, RandomIt last, const F& p)
{
using IndexType = std::decay_t<decltype(p(0))>;
IndexType n = last - first;
for (IndexType i = 0; i + 1 < n; ++i) {
IndexType ind = p(i);
while (ind < i) {
ind = p(ind);
}
using std::swap;
swap(*(first + i), *(first + ind));
}
}
或者在顶部添加一个更类似于 STL 的界面：
template<class RandomIt, class ForwardIt>
void permute(RandomIt first, RandomIt last, ForwardIt pfirst, ForwardIt plast)
{
assert(std::distance(first, last) == std::distance(pfirst, plast));
permute(first, last, [&](auto i) { return *std::next(pfirst, i); });
}
于 2019-02-17T17:40:21.770 回答
0
因此，您可以将所需元素放在数组的前面，同时在下一个迭代步骤中使用大小为 (n-1) 的剩余数组。
需要相应地调整排列数组以反映数组的减小大小。即，如果您放置在前面的元素位于“X”位置，则您需要将排列表中大于或等于 X 的所有索引减一。
在您的示例中：
array permutation -> adjusted permutation
A = {[a b c d e]} [4 3 2 0 1]
A1 = { e [a b c d]} [3 2 0 1] -> [3 2 0 1] (decrease all indexes >= 4)
A2 = { e d [a b c]} [2 0 1] -> [2 0 1] (decrease all indexes >= 3)
A3 = { e d c [a b]} [0 1] -> [0 1] (decrease all indexes >= 2)
A4 = { e d c a [b]} [1] -> [0] (decrease all indexes >= 0)
另一个例子：
A0 = {[a b c d e]} [0 2 4 3 1]
A1 = { a [b c d e]} [2 4 3 1] -> [1 3 2 0] (decrease all indexes >= 0)
A2 = { a c [b d e]} [3 2 0] -> [2 1 0] (decrease all indexes >= 2)
A3 = { a c e [b d]} [1 0] -> [1 0] (decrease all indexes >= 2)
A4 = { a c e d [b]} [0] -> [0] (decrease all indexes >= 1)
该算法虽然不是最快的，但避免了额外的内存分配，同时仍然跟踪元素的初始顺序。
于 2013-05-11T21:31:38.740 回答
0
Just a simple example C/C++ code addition to the Ziyao Wei's answer. Code is not allowed in comments, so as an answer, sorry:
for (int i = 0; i < count; ++i)
{
// Skip to the next non-processed item
if (destinations[i] < 0)
continue;
int currentPosition = i;
// destinations[X] = Y means "an item on position Y should be at position X"
// So we should move an item that is now at position X somewhere
// else - swap it with item on position Y. Then we have a right
// item on position X, but the original X-item now on position Y,
// maybe should be occupied by someone else (an item Z). So we
// check destinations[Y] = Z and move the X-item further until we got
// destinations[?] = X which mean that on position ? should be an item
// from position X - which is exactly the X-item we've been kicking
// around all this time. Loop closed.
//
// Each permutation has one or more such loops, they obvisouly
// don't intersect, so we may mark each processed position as such
// and once the loop is over go further down by an array from
// position X searching for a non-marked item to start a new loop.
while (destinations[currentPosition] != i)
{
const int target = destinations[currentPosition];
std::swap(items[currentPosition], items[target]);
destinations[currentPosition] = -1 - target;
currentPosition = target;
}
// Mark last current position as swapped before moving on
destinations[currentPosition] = -1 - destinations[currentPosition];
}
for (int i = 0; i < count; ++i)
destinations[i] = -1 - destinations[i];
(for C - replace std::swap with something else)
于 2014-12-16T15:18:50.823 回答
0
这里有一个更清晰的版本，它接受一个接受索引的 swapElements 函数，例如，std::swap(Item[cycle], Item[P[cycle]])$
本质上它会遍历所有元素并遵循循环，如果它们还没有被访问过。除了第二次检查!visited[P[cycle]]之外，我们还可以与上面其他地方完成的循环中的第一个元素进行比较。
bool visited[n] = {0};
for (int i = 0; i < n; i++) {
int cycle = i;
while(! visited[cycle] && ! visited[P[cycle]]) {
swapElements(cycle,P[cycle]);
visited[cycle]=true;
cycle = P[cycle];
}
}
于 2018-11-06T18:40:39.763 回答
0
通过检查索引来追溯我们交换的内容。
Java，O(N) 交换，O(1) 空间：
static void swap(char[] arr, int x, int y) {
char tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
public static void main(String[] args) {
int[] intArray = new int[]{4,2,3,0,1};
char[] charArray = new char[]{'A','B','C','D','E'};
for(int i=0; i<intArray.length; i++) {
int index_to_swap = intArray[i];
// Check index if it has already been swapped before
while (index_to_swap < i) {
// trace back the index
index_to_swap = intArray[index_to_swap];
}
swap(charArray, index_to_swap, i);
}
}
于 2021-04-11T06:40:56.610 回答
-1
我同意这里的许多解决方案，但下面是一个非常短的代码片段，它在整个排列周期中排列：
def _swap(a, i, j):
a[i], a[j] = a[j], a[i]
def apply_permutation(a, p):
idx = 0
while p[idx] != 0:
_swap(a, idx, p[idx])
idx = p[idx]
所以下面的代码片段
a = list(range(4))
p = [1, 3, 2, 0]
apply_permutation(a, p)
print(a)
输出[2, 4, 3, 1]
于 2018-09-13T14:26:36.813 回答