面试题：替换两个数组在内存中的位置

Question

给定两个连续的数组，

A

和

B

。它们看起来像

int AandB[] = {a1,a2,...,am,b1,b2,...,bn};

您需要编写一个程序来交换数组

A

和

B

在内存中的顺序，以便

B

出现在

A

之前。在我们的示例中，

AandB

应该变成

int AandB[] = {b1,b2,...,bn,a1,...,am};

最有效的方法是什么？

Answer 1

三数组反转：

(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--;
    }
}

Answer 2

我的回答：

首先，我假设

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

元素解决相同的问题。但这可能效率不高。

还有一些细节我省略了，但无论如何面试官告诉我这不是可行的方法，并且有一些非常聪明但也很简单的解决方案。

Answer 3

您想要进行的变换本质上是按

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);
}

Answer 4

嗯，一边打字一边思考...

我假设“在内存中”你不能通过创建一个或多个新数组来作弊，即使是临时数组。我还将假设您可以有一个临时变量（否则交换内容会变得非常棘手）。

看起来你的两个子数组可以有不同的大小，所以你不能只是将 a1 与 b1 交换，a2 与 b2 交换，等等

所以你需要弄清楚“a”数组元素首先从哪里开始。你可以通过找到“n”来做到这一点。然后，您必须重复保存第一个剩余的“a”元素，并将第一个剩余的“b”元素放在那里。

现在事情变得棘手了。您需要将保存的“a”元素放入其正确的位置，但这可能包含未交换的元素。最简单的方法可能是将所有剩余元素上移一位，并将保存的“a”放在末尾。如果你反复这样做，你最终会把所有东西都放在正确的位置。如果数组很大的话，就会有很多变化。

我相信稍微复杂一点的算法可以只对增量中的元素（第一个“q”元素，其中“q”是数组大小之间的增量）进行移位，并且仅在增量区域中工作时进行。之后就只是简单的交换了。

Answer 5

我们可以使用 php 中的 array_merge。

首先使用array_splice()来分割这些数组，然后使用上面的函数。这是针对 php 的。