给定两个连续的数组,
A
和B
。它们看起来像
int AandB[] = {a1,a2,...,am,b1,b2,...,bn};
您需要编写一个程序来交换数组
A
和B
在内存中的顺序,以便B
出现在A
之前。在我们的示例中,AandB
应该变成
int AandB[] = {b1,b2,...,bn,a1,...,am};
最有效的方法是什么?
三数组反转:
(a1 a2 a3 a4 a5 b1 b2 b3)
b3 b2 b1 a5 a4 a3 a2 a1
(b3 b2 b1)a5 a4 a3 a2 a1
b1 b2 b3 a5 a4 a3 a2 a1
b1 b2 b3(a5 a4 a3 a2 a1)
b1 b2 b3 a1 a2 a3 a4 a5
使用带有开始和结束的“rev”函数来表达:
rev(AandB, 0, n+m)
rev(AandB, 0, m)
rev(AandB, m, n)
对于修订(为了清楚起见,省略类型等):
rev(x, i, j) {
j--; // j points to one after the subarray we're reversing
while (i < j) {
tmp = x[i];
x[i] = x[j];
x[j] = tmp;
i++;
j--;
}
}
我的回答:
首先,我假设
m<n
。
由于每个排列都可以分解为不相交的循环,因此需要
a1,...,am,b1,..,bn
到 b1,..,bn,a1,...,am
的排列也可以分解。由于给定了索引i
,很容易计算p(i)
(假设wlog为m<n
,那么如果i<=m
,我们有p(i)=n+i
,如果i>m
我们有p(i)=i-m
)。
我们可以从
AandB[i]
开始,将其值移至p(i)=j
,然后,将AandB[j]
中的值移至p(j)
,依此类推。由于排列可以分解为不相交的循环,因此我们最终会得到在i
。
我们只需要跟踪我们已经移动了哪些元素。可以证明,在我们的例子中,排列中的任何循环都不会包含
A
的两个连续元素,因此我认为跟踪我们订购了 A
的多少个元素就足够了。
另一个效率不高的简单选项是注意 给定
{a1,...,am,b1,...bn}
,可以将 a1..am
替换为 b(n-m)..b(n)
,得到 {b(n-m)...b(n),b(1)..b(m),a1..am}
。现在通过递归,为数组的第一个 n
元素解决相同的问题。但这可能效率不高。
还有一些细节我省略了,但无论如何面试官告诉我这不是可行的方法,并且有一些非常聪明但也很简单的解决方案。
您想要进行的变换本质上是按
n
(或按 m
,具体取决于移位的方向)进行循环移位。
例如,我们有
1 2 3 4 5 6 7 a b c
(我使用字母和数字来分隔两个数组)
在此变换过程中,1
将移动到4
的位置,4
将移动到7
,7
移动到c
,c
移动到3
,3
移动到6
等等。最终,我们将返回到开始的位置1
。唯一的技巧是,有时我们会在完成整个转换之前返回到
1
。就像 1 2 a b c d
的情况一样,位置将为 1 -> a -> c -> 1
。在这种情况下,我们需要从2
开始并重复操作。
您可以注意到,我们需要的重复次数是
n
和 m
的最大公约数。
所以,代码可能看起来像这样
int repetitions = GCD(n, m);
int size = n + m;
for (int i = 0; i < repetitions; ++i) {
int current_number = a[i];
int j = i;
do {
j = (j + n) % size;
int tmp = current_number;
current_number = a[j];
a[j] = tmp;
} while (j != i);
}
可以使用
众所周知的递归公式在
O(logn)
中轻松计算最大公约数。
编辑
它确实有效,我在Java中尝试过。为了便于表示,我仅将数据类型更改为字符串。
String[] a = {"1", "2", "3", "4", "5", "6", "a", "b", "c"};
int n = 3;
int m = 6;
// code from above...
System.out.println(Arrays.toString(a));
还有欧几里得公式:
int GCD(int a, int b) {
if (a == 0) {
return b;
}
return GCD(b % a, a);
}
嗯,一边打字一边思考...
我假设“在内存中”你不能通过创建一个或多个新数组来作弊,即使是临时数组。我还将假设您可以有一个临时变量(否则交换内容会变得非常棘手)。
看起来你的两个子数组可以有不同的大小,所以你不能只是将 a1 与 b1 交换,a2 与 b2 交换,等等
所以你需要弄清楚“a”数组元素首先从哪里开始。你可以通过找到“n”来做到这一点。然后,您必须重复保存第一个剩余的“a”元素,并将第一个剩余的“b”元素放在那里。
现在事情变得棘手了。您需要将保存的“a”元素放入其正确的位置,但这可能包含未交换的元素。最简单的方法可能是将所有剩余元素上移一位,并将保存的“a”放在末尾。如果你反复这样做,你最终会把所有东西都放在正确的位置。如果数组很大的话,就会有很多变化。
我相信稍微复杂一点的算法可以只对增量中的元素(第一个“q”元素,其中“q”是数组大小之间的增量)进行移位,并且仅在增量区域中工作时进行。之后就只是简单的交换了。
我们可以使用 php 中的 array_merge。
首先使用array_splice()来分割这些数组,然后使用上面的函数。这是针对 php 的。