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

Question

给定两个连续的数组，A和B。它们看起来像这样：

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

您需要编写一个程序，将数组A和B在内存中的顺序交换，使得B出现在A之前。在我们的例子中，AandB应该变成BandA。请注意，您需要保留HTML标记。

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

什么是最有效的方法来做到这一点？

- Elazar Leibovich

---

a1 是某个元素 A，它不需要排序或与任何其他元素进行比较，只需向前移动 m 个位置即可。 - Elazar Leibovich

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（为了清晰起见，省略类型等）：

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

- user295691

---

我不确定这是最有效的解决方案，但肯定是简单而酷炫的！没想到吧！ - Elazar Leibovich

刚刚与面试官核实，这就是他所说的解决方案，虽然优雅但比基于排列的解决方案效率低。 - Elazar Leibovich

就效率而言，我认为我们可以同意两者都是O(n)时间复杂度和O(1)空间复杂度。这个解决方案需要(n/2 + m/2 + (n+m)/2) * 3 = 3*(n+m)次交换。大小为n的循环置换需要n+1次赋值（如果包括tmp），而置换版本分解为GCD(m,n)长度为(m+n)/GCD(m,n)的循环，总共需要GCD(m,n)*((m+n)/GCD(m,n)+1)= m + n + GCD(m,n)次赋值。因此，不太高效是公平的，但在大O意义上并非如此。 - user295691

当然，我并不是指在大O表示法中它的效率更低。我认为你对排列解决方案的效率计算过于复杂了。在我的解决方案中，您只需一次访问每个元素。将元素放置在正确位置后，它就消失了。因此，我们有m+n个内存访问，并添加了“常数” log（m+n） （计算GCD的成本）。在你的情况下，我需要三次访问每个元素，所以需要进行3*（m+n）次交换。但还是谢谢！ - Elazar Leibovich

Answer 2

我的回答：

首先，我假设 m<n。

由于每个排列都可以分解成不相交的循环，因此可以将将 a1,...,am,b1,..,bn 转换为 b1,..,bn,a1,...,am 的置换也可以。并且，由于给定一个索引 i，很容易计算出 p(i)（假设 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}，可以用 b(n-m)..b(n) 替换 a1..am，得到 {b(n-m)...b(n),b(1)..b(m),a1..am}。现在通过递归，为数组的前 n 个元素解决相同的问题。但这可能不太有效。

还有一些我省略的细节，但无论如何面试官告诉我这不是正确的方法，而且有一个非常聪明且简单的解决方案。

- Elazar Leibovich

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

- Nikita Rybak

---

这基本上是我的解决方案，尽管我没有证明循环次数是“GCD(n,m)”。谢谢！ - Elazar Leibovich

@Elazar 噢 :) 看起来很理论化，我无法完成它，所以直接跳转到代码了 :) +1 - Nikita Rybak

Answer 4

好的，在这里打字时思考一下...

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

看起来你的两个子数组的大小可能不同，因此你不能只是交换a1和b1，a2和b2等。

所以你需要先找出“a”数组元素的起始位置。你可以通过找到“n”来实现这一点。然后你需要反复保存第一个剩余的“a”元素，并将第一个剩余的“b”元素放在那里。

现在问题来了。你需要把保存的“a”元素放到它应该在的位置，但那里可能包含一个未交换的元素。最简单的方法可能是将所有剩余的元素向上移动一个位置，并将保存的“a”放在末尾。如果你反复这样做，最终就会得到正确的结果。但如果数组很大，这样做需要大量的移位操作。

我相信一个稍微复杂一点的算法可以只对 delta（即两个数组大小之间的差值）中的元素进行移动，而且仅在 delta 区域内工作。在那之后，它只需要进行简单的交换操作。

- T.E.D.

Answer 5

我们可以在 PHP 中使用 array_merge。

首先使用 array_splice() 将这些数组拆分，然后再使用上述函数。这是针对 PHP 的。

- ayush

---

这是一个面试问题，而不是 PHP 问题，array_merge 函数并不假设 A 和 B 在内存中是连续的。 - Elazar Leibovich

不，我不相信你可以这样做。这似乎需要目标数组与源数组位于不同的内存区域。 - T.E.D.