Gia*_*epo 1 c++ arrays algorithm permutation
考虑一个数组。根据另一个提供元素新位置的数组(不先复制该数组的副本),将其元素置换的好方法是什么?
例如
int a[]={37,43,5,10}; //array to permute
int b[]={3,1,4,2}; //new position of each element
Run Code Online (Sandbox Code Playgroud)
所以一个应该成为
{43,10,37,5}
Run Code Online (Sandbox Code Playgroud)
我自然想到了制作a的副本,然后在新位置重新分配其元素。但是有没有一种方法可以不复制数组(即更简单的方法)呢?
注意:如果可能的话,不应使用特定的C ++标头,而应仅使用<iostream>
通过一次处理一个置换数组的周期,可以在 O(n) 时间内使用 O(1) 额外内存完成。
注意:此方法比此特定设置所需的更复杂(a并且b都是 int 数组),但它有一些好处:
它可以处理任意数据类型(例如,置换数组a可以是字符串数组)。
它可以保留b置换数组中的原始值。
考虑最初的例子:
int a[] = {37, 43, 5, 10}; // array to permute
int b[] = { 3, 1, 4, 2}; // new position of each element
Run Code Online (Sandbox Code Playgroud)
该数组b表明我们要进行以下分配链:
a[1] <-- a[3] <-- a[4] <-- a[2] <-- a[1].
问题是在最后一次分配中,我们不再具有访问权限a[1](它已被替换为a[3])。
然而,起始元素的原始值可以保存在一个辅助变量中,以便我们在关闭循环时使用它(保证当我们关闭循环时,我们将精确到达我们开始的元素 - 否则某些元素可以通过多种方式访问,即我们将有 b[i] = b[j]),对于某些 i != j)。
一般来说,排列可能包含多个循环。在处理完一个循环之后,我们需要从一个尚未更新的元素开始(即它目前不是循环处理的一部分)。
因此,我们需要知道到目前为止哪些元素没有被处理。
一种可能的方法是临时修改置换向量b以跟踪更新了哪些元素,例如,b在更新 中的元素时取消相应位置中的值a。这样做的好处是最后,我们可以遍历所有元素b并恢复初始值(通过再次否定所有元素)。
下面是之前的想法的实现。
int main() {
int a[] = {11, 22, 33, 44};
int b[] = { 2, 1, 4, 3};
int aux, crtIdx, nxtIdx;
int n = sizeof(a) / sizeof(a[0]);
for (int i = 0; i < n; i++) {
// check whether the i'th element
// was already processed
if (b[i] < 0) {
continue;
}
// start processing of a new cycle;
// backup the first value to aux
aux = a[i];
crtIdx = i;
nxtIdx = b[i] - 1;
// advance along the cycle until we reach
// again the first element
while (nxtIdx != i) {
a[crtIdx] = a[nxtIdx];
// use the b array to mark that the
// element at crtIdx was updated
b[crtIdx] = -b[crtIdx];
crtIdx = nxtIdx;
nxtIdx = b[nxtIdx] - 1;
}
// finalize the cycle using the aux variable
a[crtIdx] = aux;
b[crtIdx] = -b[crtIdx];
}
// restore the original values of b[i]
for (int i = 0; i < n; i++) {
b[i] = -b[i];
}
}
Run Code Online (Sandbox Code Playgroud)
注意:虽然代码包含两个嵌套循环,但时间复杂度为 O(n)。考虑到每个元素只更新一次这一事实可以看出这一点(如果我们到达一个已经处理过的元素,则立即继续外部循环)。
我将在这里展示算法执行的主要步骤,使用这个例子:
a = {11, 22, 33, 44}
b = { 2, 1, 4, 3}
Run Code Online (Sandbox Code Playgroud)
步骤 1.
我们查看第一个元素(请查看代码中的外部for循环i)。第一个元素不是已处理循环的一部分,因此我们开始处理新循环。我们通过存储aux这个元素的初始值来实现。
a = {11, 22, 33, 44}
b = { 2, 1, 4, 3}
aux = 11
Run Code Online (Sandbox Code Playgroud)
第 2 步。
我们继续这个循环,更新元素,将它们标记为已更新(通过否定b数组中的相应元素),直到我们再次到达第一个元素。
a = {22, 22, 33, 44}
b = {-2, 1, 4, 3}
aux = 11
Run Code Online (Sandbox Code Playgroud)
第 3 步。 我们再次到达循环的第一个元素,需要它的初始值来更新循环的最后一个元素。这是我们使用辅助变量的地方。这样,第一个循环就完成了。
a = {22, 11, 33, 44}
b = {-2, -1, 4, 3}
aux = 11
Run Code Online (Sandbox Code Playgroud)
第 4 步。
我们继续外循环(forover i)。我们看到第二个元素已经被处理(因为b[1]是负数),因此我们不会在这里开始一个新的循环。我们继续,并在第三个元素(尚未处理)处开始一个新循环。
现在我们可以重用相同的aux变量来备份这个循环的第一个元素(我们不再需要保存第一个循环的值,因为那个循环已经完全解决了)。
a = {22, 11, 33, 44}
b = {-2, -1, 4, 3}
aux = 33
Run Code Online (Sandbox Code Playgroud)
步骤5. 第二个循环的处理以前面步骤中描述的类似方式进行,结果是这样的:
a = {22, 11, 44, 33}
b = {-2, -1, -4, -3}
aux = 33
Run Code Online (Sandbox Code Playgroud)
第六步
,循环i继续,没有发现未处理的元素。现在,我们知道所有元素都被处理了,我们可以否定每个元素b以恢复原始值。
a = {22, 11, 44, 33}
b = { 2, 1, 4, 3}
Run Code Online (Sandbox Code Playgroud)
最简单的答案是复制a到b,并随即销毁b:
for (i = 0; i < B_SIZE; ++i):
b[i] = a[b[i] - 1];
Run Code Online (Sandbox Code Playgroud)
然后,如果需要,只需复制b回a:
for (i = 0; i < B_SIZE; ++i):
a[i] = b[i];
Run Code Online (Sandbox Code Playgroud)
由于a和b都是int数组,因此您不会浪费任何多余的内存。您以中的正确值结束a,而没有使用比给您的内存更多的内存。这不是最大效率(尽管它是O(n)),但是最容易理解。