假设我有一个数组A，其中包含范围在[0，n)内的n个唯一元素。换句话说，我拥有[0，n)整数的排列。
是否可能使用O(1)额外空间（即原地）将 A 转换为 B ，使得 B[A[i]] = i？
例如：
A B
[3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4]
能否使用恒定的额外空间反转数组？
29
- orlp
9
我们可以使用数组条目的符号位来编码信息吗？还是这会违背不使用额外空间的思想？ - Niklas B.
这真的取决于模型。例如，在经典的RAM模型中，我们有log n < w，因此我们不会通过使用w - log n位来“浪费”空间。那么你的模型是什么？ - Niklas B.
1@NiklasB。如果您想要具体一些，可以参考Transdichotomous模型。 - orlp
@orlp：为什么这是O（N）空间复杂度？您可以使用已经分配的数组中的1位。您不需要单独分配N个位。 - Cratylus
1这似乎更适合放在 [CS.SE] 上。 - Bergi
显示剩余4条评论
5个回答
24
是的，可以使用O(n^2)时间复杂度的算法实现：
从索引0开始，将该元素的值设为0，并将0写入由该元素索引的单元格中。然后使用被覆盖的元素来获取下一个索引并在那里写入上一个索引。继续直到返回到索引0。这是循环主元算法。
然后从索引1、2等位置开始重复同样的过程。但在做任何更改之前，对于此索引，请使用不带任何修改的循环主元算法进行操作。如果此循环包含任何低于起始索引的索引，则跳过它。
或者使用O(n^3)时间复杂度的算法：
从索引0开始，将该元素的值设为0，并将0写入由该元素索引的单元格中。然后使用被覆盖的元素来获取下一个索引并在那里写入上一个索引。继续直到返回到索引0。
然后从索引1、2等位置开始重复同样的过程。但在做任何更改之前，请对所有先前的索引使用不带任何修改的循环主元算法进行操作。如果当前索引存在于任何先前的循环中，则跳过它。
我已经编写了（稍微优化的）C++11实现来确定如果随机排列被反转，每个元素平均需要多少额外访问。这里是结果：
size accesses
2^10 2.76172
2^12 4.77271
2^14 6.36212
2^16 7.10641
2^18 9.05811
2^20 10.3053
2^22 11.6851
2^24 12.6975
2^26 14.6125
2^28 16.0617
尽管大小呈指数增长，但元素访问数量几乎呈线性增长，因此对于随机排列的预期时间复杂度大约为O(n log n)。
- Evgeny Kluev
1
2有一个Theta(n log n)期望复杂度的证明，其中我们展示了迭代“j”在期望中进行约n / (j + 1)次读取（该数字是“带替换”的；我认为校正项是低阶的，虽然）。 - David Eisenstat
0
反转数组A需要我们找到一个排列B，满足对于所有的i，A[B[i]]=i。
为了原地构建逆序数组，我们必须通过设置A[A[i]]=i来交换元素和索引，对于每个元素A[i]。显然，如果我们只是简单地遍历A并执行上述替换，我们可能会覆盖A中即将出现的元素，导致计算失败。
因此，我们必须沿着A的循环交换元素和索引，按照c=A[c]的方式进行，直到我们到达循环的起始索引c=i。
A的每个元素都属于这样一个循环。由于我们没有空间来存储一个元素A[i]是否已经被处理并且需要跳过，所以我们必须遵循它的循环：如果我们到达一个索引cThis algorithm has a worst-case run-time complexity of O(n²), an average run-time complexity of O(n log n) and a best-case run-time complexity of O(n).
为了原地构建逆序数组，我们必须通过设置A[A[i]]=i来交换元素和索引，对于每个元素A[i]。显然，如果我们只是简单地遍历A并执行上述替换，我们可能会覆盖A中即将出现的元素，导致计算失败。
因此，我们必须沿着A的循环交换元素和索引，按照c=A[c]的方式进行，直到我们到达循环的起始索引c=i。
A的每个元素都属于这样一个循环。由于我们没有空间来存储一个元素A[i]是否已经被处理并且需要跳过，所以我们必须遵循它的循环：如果我们到达一个索引cThis algorithm has a worst-case run-time complexity of O(n²), an average run-time complexity of O(n log n) and a best-case run-time complexity of O(n).
function invert(array) {
main:
for (var i = 0, length = array.length; i < length; ++i) {
// check if this cycle has already been traversed before:
for (var c = array[i]; c != i; c = array[c]) {
if (c <= i) continue main;
}
// Replacing each cycle element with its predecessors index:
var c_index = i,
c = array[i];
do {
var tmp = array[c];
array[c] = c_index; // replace
c_index = c; // move forward
c = tmp;
} while (i != c_index)
}
return array;
}
console.log(invert([3, 1, 0, 2, 4])); // [2, 1, 3, 0, 4]针对 A = [1, 2, 3, 0] 的示例：
索引为0的第一个元素1属于元素1-2-3-0的循环。一旦我们沿着这个循环移动索引0、1、2和3，我们就完成了第一步。
索引为1的下一个元素0也属于同一个循环，我们的检查告诉我们只需要进行一步操作（因为它是向后的一步）。
对于剩余的元素1和2也是如此。
总共，我们执行了4 + 1 + 1 + 1次“操作”。这是最佳情况。
- le_m
0
以下方法优化了循环遍历，如果已经处理过，则会更加高效。此外，每个元素都是基于1的。在尝试访问给定数组中的元素时需要相应地进行转换。
#include <stdio.h>
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
// helper function to traverse cycles
void cycle(int i, vector<int>& A) {
int cur_index = i+1, next_index = A[i];
while (next_index > 0) {
int temp = A[next_index-1];
A[next_index-1] = -(cur_index);
cur_index = next_index;
next_index = temp;
if (i+1 == abs(cur_index)) {
break;
}
}
}
void inverse_permutation(vector<int>& A) {
for (int i = 0; i < A.size(); i++) {
cycle(i, A);
}
for (int i = 0; i < A.size(); i++) {
A[i] = abs(A[i]);
}
for (int i = 0; i < A.size(); i++) {
cout<<A[i]<<" ";
}
}
int main(){
// vector<int> perm = {4,0,3,1,2,5,6,7,8};
vector<int> perm = {5,1,4,2,3,6,7,9,8};
//vector<int> perm = { 17,2,15,19,3,7,12,4,18,20,5,14,13,6,11,10,1,9,8,16};
// vector<int> perm = {4, 1, 2, 3};
// { 6,17,9,23,2,10,20,7,11,5,14,13,4,1,25,22,8,24,21,18,19,12,15,16,3 } =
// { 14,5,25,13,10,1,8,17,3,6,9,22,12,11,23,24,2,20,21,7,19,16,4,18,15 }
// vector<int> perm = {6, 17, 9, 23, 2, 10, 20, 7, 11, 5, 14, 13, 4, 1, 25, 22, 8, 24, 21, 18, 19, 12, 15, 16, 3};
inverse_permutation(perm);
return 0;
}
- Avaneendra Alugupalli
0
在 Python 中实现此 说明：
def inverse_permutation_zero_based(A):
"""
Swap elements and indices along cycles of A by following `c = A[c]` until we reach
our cycle's starting index `c = i`.
Every element of A belongs to one such cycle. Since we have no space to store
whether or not an element A[i] has already been processed and needs to be skipped,
we have to follow its cycle: If we reach an index c < i we would know that this
element is part of a previously processed cycle.
Time Complexity: O(n*n), Space Complexity: O(1)
"""
def cycle(i, A):
"""
Replacing each cycle element with its predecessors index
"""
c_index = i
c = A[i]
while True:
temp = A[c]
A[c] = c_index # replace
c_index = c # move forward
c = temp
if i == c_index:
break
for i in range(len(A)):
# check if this cycle has already been traversed before
j = A[i]
while j != i:
if j <= i:
break
j = A[j]
else:
cycle(i, A)
return A
>>> inverse_permutation_zero_based([3, 1, 0, 2, 4])
[2, 1, 3, 0, 4]
- Brayoni
0
如果我们尝试在单个位置存储2个数字，那么可以在O(n)时间复杂度和O(1)空间内完成此操作。
First, let's see how we can get 2 values from a single variable. Suppose we have a variable x and we want to get two values from it, 2 and 1. So,
x = n*1 + 2 , suppose n = 5 here.
x = 5*1 + 2 = 7
Now for 2, we can take remainder of x, ie, x%5. And for 1, we can take quotient of x, ie , x/5
and if we take n = 3
x = 3*1 + 2 = 5
x%3 = 5%3 = 2
x/3 = 5/3 = 1
我们知道这里的数组包含在范围[0，n-1]内的值，因此我们可以将除数取为数组的大小n。因此，我们将使用上述概念在每个索引处存储2个数字，一个表示旧值，另一个表示新值。
A B
0 1 2 3 4 0 1 2 3 4
[3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4]
.
a[0] = 3, that means, a[3] = 0 in our answer.
a[a[0]] = 2 //old
a[a[0]] = 0 //new
a[a[0]] = n* new + old = 5*0 + 2 = 2
a[a[i]] = n*i + a[a[i]]
在数组遍历期间，a[i]的值可能大于n，因为我们正在修改它。因此，我们将使用a[i]%n来获取旧值。 因此，逻辑应该是：
a[a[i]%n] = n*i + a[a[i]%n]
Array -> 13 6 15 2 24
现在，要获取旧值，请取每个值除以n的余数；要获取新值，只需将每个值除以n，在本例中n=5。
Array -> 2 1 3 0 4
- Nancy
1
这是一个不错的想法，但只有在数据类型比所需更大时才有效。例如，在C中反转256个
uint8_t数组时，它将无法工作。 - orlp网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接