是否可以反转具有常量额外 space 的数组？
Is it possible to invert an array with constant extra space?
假设我有一个数组 A，其中 n 个唯一元素位于 [0, n)[ 范围内=24=]。换句话说，我有一个整数 [0, n].
的排列
可以将 A 转换为 B 使用 O(1) 额外的 space （也就是就地）这样B[A[i]] = i?
例如：
A B
[3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4]
是的，有可能，用 O(n^2) 时间算法：
获取索引为 0 的元素，然后将 0 写入该元素索引的单元格。然后使用刚刚覆盖的元素获取下一个索引并在那里写入前一个索引。继续，直到回到索引 0。这是循环领导者算法。
然后从索引 1、2 开始执行相同的操作，...但是在进行任何更改之前，请执行循环领导者算法，而不从该索引开始进行任何修改。如果此循环包含起始索引下方的任何索引，则跳过它。
或者这个O(n^3)时间的算法：
获取索引为 0 的元素，然后将 0 写入该元素索引的单元格。然后使用刚刚覆盖的元素获取下一个索引并在那里写入前一个索引。继续，直到返回索引 0。
然后从索引 1、2、... 开始执行相同的操作，但在进行任何更改之前，请从所有前面的索引开始执行循环领导者算法而不进行任何修改。如果当前索引存在于任何前面的循环中，则跳过它。
我已经在 C++11 中编写了（稍微优化）implementation 的 O(n^2) 算法来确定如果随机排列被反转，每个元素平均需要多少次额外访问。以下是结果：
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)。
反转数组 A 需要我们找到满足所有 i.
要求 A[B[i]] == i 的排列 B
要就地构建逆，我们必须通过为每个元素 A[i] 设置 A[A[i]] = i 来交换元素和索引。显然，如果我们简单地遍历 A 并执行上述替换，我们可能会覆盖 A 中即将到来的元素，并且我们的计算将失败。
因此，我们必须按照 c = A[c] 沿着 A 的循环交换元素和索引，直到我们到达循环的起始索引 c = i。
A的每个元素都属于一个这样的循环。由于我们没有 space 来存储元素 A[i] 是否已经被处理并且需要被跳过，我们必须遵循它的循环：如果我们到达索引 c < i 我们将知道此元素是先前处理的循环的一部分。
该算法的最坏情况 运行 时间复杂度为 O(n²)，平均 运行 时间复杂度为 O(n log n) 和最佳情况 运行-时间复杂度为 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 'operations'。这是最好的情况。
在 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]
这可以在 O(n) 时间复杂度和 O(1) space 中完成，如果我们尝试在一个位置存储 2 个数字。
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
假设我有一个数组 A，其中 n 个唯一元素位于 [0, n)[ 范围内=24=]。换句话说，我有一个整数 [0, n].
的排列可以将 A 转换为 B 使用 O(1) 额外的 space （也就是就地）这样B[A[i]] = i?
例如：
A B
[3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4]
是的，有可能，用 O(n^2) 时间算法：
获取索引为 0 的元素，然后将 0 写入该元素索引的单元格。然后使用刚刚覆盖的元素获取下一个索引并在那里写入前一个索引。继续，直到回到索引 0。这是循环领导者算法。
然后从索引 1、2 开始执行相同的操作，...但是在进行任何更改之前，请执行循环领导者算法，而不从该索引开始进行任何修改。如果此循环包含起始索引下方的任何索引，则跳过它。
或者这个O(n^3)时间的算法：
获取索引为 0 的元素，然后将 0 写入该元素索引的单元格。然后使用刚刚覆盖的元素获取下一个索引并在那里写入前一个索引。继续，直到返回索引 0。
然后从索引 1、2、... 开始执行相同的操作，但在进行任何更改之前，请从所有前面的索引开始执行循环领导者算法而不进行任何修改。如果当前索引存在于任何前面的循环中，则跳过它。
我已经在 C++11 中编写了（稍微优化）implementation 的 O(n^2) 算法来确定如果随机排列被反转，每个元素平均需要多少次额外访问。以下是结果：
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)。
反转数组 A 需要我们找到满足所有 i.
A[B[i]] == i 的排列 B
要就地构建逆，我们必须通过为每个元素 A[i] 设置 A[A[i]] = i 来交换元素和索引。显然，如果我们简单地遍历 A 并执行上述替换，我们可能会覆盖 A 中即将到来的元素，并且我们的计算将失败。
因此，我们必须按照 c = A[c] 沿着 A 的循环交换元素和索引，直到我们到达循环的起始索引 c = i。
A的每个元素都属于一个这样的循环。由于我们没有 space 来存储元素 A[i] 是否已经被处理并且需要被跳过，我们必须遵循它的循环：如果我们到达索引 c < i 我们将知道此元素是先前处理的循环的一部分。
该算法的最坏情况 运行 时间复杂度为 O(n²)，平均 运行 时间复杂度为 O(n log n) 和最佳情况 运行-时间复杂度为 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 'operations'。这是最好的情况。
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]
这可以在 O(n) 时间复杂度和 O(1) space 中完成，如果我们尝试在一个位置存储 2 个数字。
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