如何掌握就地阵列修改算法？ [英] How to master in-place array modification algorithms?

问题描述

我是preparing的软件面试，和我有就地阵列修改的麻烦。例如，在输出洗牌问题你交织阵列的两半，这样，1 2 3 4 5 6 7 8将成为1 5 2 6 3 7 4 8的这个问题要求恒定的内存解决方案（和线性时间，但我不知道这甚至有可能）。

I am preparing for a software job interview, and I have trouble with in-place array modifications. For example, in the out-shuffle problem you interleave two halves of an array, so that 1 2 3 4 5 6 7 8 would become 1 5 2 6 3 7 4 8. This question asks for a constant-memory solution (and linear-time, although I'm not sure that's even possible).

首先，我想到了一个线性算法是微不足道的，但我不能工作了。然后，我发现了一个简单为O（n ^ 2）算法，但我花了很长的时间。我仍然没有找到一个更快的解决方案。

First I thought a linear algorithm is trivial, but then I couldn't work it out. Then I did find a simple O(n^2) algorithm but it took me a long time. And I still don't find a faster solution.

我记得也有麻烦解决从宾利的编程珠玑类似的问题，columnn 2：旋转通过我的位置留下一个数组（如ABCDE 2旋转变得cdeab），在时间 O（N）键，只需几个字节的额外空间。

I remember also having trouble solving a similar problem from Bentley's Programming Pearls, columnn 2: Rotate an array left by i positions (e.g. abcde rotated by 2 becomes cdeab), in time O(n) and with just a couple of bytes extra space.

有没有人有技巧，帮助环绕这样的问题我的头？对于这样的问题有具体的教程？谢谢！

Does anyone have tips that help wrap my head around such problems? Are there specific tutorials for such questions? Thanks!

推荐答案

关于一个O（n）时间，O（1）空间算法进行了洗牌的

About an O(n) time, O(1) space algorithm for out-shuffle

做一个彻头彻尾的洗牌在O（n）时间及O（1）空间是可能的，但它的的艰难的。不知道为什么人们认为它很容易，并且建议你尝试其他的东西。

Doing an out-shuffle in O(n) time and O(1) space is possible, but it is tough. Not sure why people think it is easy and are suggesting you try something else.

下面的文章有一个O（n）时间及O（1）空间的解决方案（尽管它是inshuffle，但这样做inshuffle使得outshuffle简单）：

The following paper has an O(n) time and O(1) space solution (though it is for inshuffle, but doing inshuffle makes outshuffle trivial):

<一个href="http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf">http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf

关于方法来解决就地阵列修改算法的

About a method to tackle in-place array modification algorithms

在就地修改算法会变得非常的硬盘的处理。

In-place modification algorithms could become very hard to handle.

考虑几个：

• 在就地进行洗牌的线性时间。使用数论。
• 在就地归并排序，是开了几年。一种算法来了，但太复杂而不实用。使用非常复杂的簿记。

抱歉，如果这听起来令人沮丧，但没有灵丹妙药，这将解决所有原地算法的问题给你。你需要的问题的工作，找出它的属性，并试图利用这些漏洞（如大多数算法的情况下）。

Sorry, if this sounds discouraging, but there is no magic elixir which will solve all in-place algorithm problems for you. You need to work with the problem, figure out its properties and try to exploit them (as is the case with most algorithms).

也就是说，对于数组修改其导致的置换原数组的的，你可以尝试的方法如下置换的周期。基本上，任意排列可以写成一个不相交集的周期（参见约翰的回答也是如此）。例如置换：

That said, for array modifications which result in a permutation of the original array, you can try the method of following the cycles of the permutation. Basically any permutation can be written as a disjoint set of cycles (see John's answer too). For instance the permutation:

1 4 2 5 3 6

的 1 2 3 4 5 6 可以写成

1 -> 1
2 -> 3 -> 5 -> 4 -> 2
6 -> 6.

您可以阅读箭头'去'。

you can read the arrow as 'goes to'.

因此​​重排的阵列 1 2 3 4 5 6 您遵循三个周期：

So to permute the array 1 2 3 4 5 6 you follow the three cycles:

1变为1。

6变为6。

2前进到3，3转到5,5进到4和4进到2

2 goes to 3, 3 goes to 5, 5 goes to 4 and 4 goes to 2.

要遵循这一周期长，你可以只使用一个临时变量。商店3在它。把2，其中3了。现在把3在5和5存储在临时等。既然你只使用恒定的额外临时空间按照特定的周期，你正在做的就地修改数组的循环。

To follow this long cycle, you can use just one temp variable. Store 3 in it. Put 2 where 3 was. Now put 3 in 5 and store 5 in the temp and so on. Since you only use constant extra temp space to follow a particular cycle, you are doing an in-place modification of the array for that cycle.

现在，如果我给你一个公式来计算，其中的元素去，你现在需要的是一组启动每个周期的元素。

Now if I gave you a formula for computing where an element goes to, all you now need is the set of starting elements of each cycle.

周期的起始点的明智选择可以使该算法容易。如果你拿出在O（1）空间中的起点，你现在有一个完整的原地算法。这是你实际上可能以熟悉的问题，并利用它的属性。

A judicious choice of the starting points of the cycles can make the algorithm easy. If you come up with the starting points in O(1) space, you now have a complete in-place algorithm. This is where you might actually have to get familiar with the problem and exploit its properties.

即使你不知道如何计算周期的起点，但有一个公式来计算的下一个元素，你可以用这个方法来获取就地O（n）时间的算法在某些特殊案例。

Even if you didn't know how to compute the starting points of the cycles, but had a formula to compute the next element, you could use this method to get an O(n) time in-place algorithm in some special cases.

例如：如果你知道仅持有正整数符号整数数组。

For instance: if you knew the array of signed integers held only positive integers.

您现在可以按照周期，但否认其中的数字为参观分子的一个指标。现在你可以走了数组，拿起你遇到的第一个正数，并按照周期的，使得周期的负面的因素，并继续寻找不变的元素。最后你只要把所有的元素正再次获得所产生的置换。

You can now follow the cycles, but negate the numbers in them as an indicator of 'visited' elements. Now you can walk the array and pick the first positive number you come across and follow the cycles for that, making the elements of the cycle negative and continue to find untouched elements. In the end you just make all the elements positive again to get the resulting permutation.

您得到一个O（n）时间及O（1）空间算法！当然，我们那种通过使用整数数组的符号位作为我们个人的访问位图被骗。

You get an O(n) time and O(1) space algorithm! Of course, we kind of 'cheated' by using the sign bits of the array integers as our personal 'visited' bitmap.

即使数组不一定是整数，这种方法（下面的周期，符号位:-)不是黑客）可以实际用于解决这两个问题，你的状态：

Even if the array was not necessarily integers, this method (of following the cycles, not the hack of sign bits :-)) can actually be used to tackle the two problems you state:

• 的inshuffle（或出洗牌）问题：当2N + 1是3的力量，它可以显示（用数论）的1 ，3,3 ^ 2，等等都在不同的周期和全部循环使用的覆盖。用事实inshuffle易受分而治之，你会得到一个O结合这（n）时间，O（1）空间算法（计算公式为I - > 2 * I模2N + 1）。请参阅上述文件的更多细节。

• The inshuffle (or out-shuffle) problem: When 2n+1 is a power of 3, it can be shown (using number theory) that 1,3,3^2, etc are in different cycles and all cycles are covered using those. Combine this with the fact that the inshuffle is susceptible to divide and conquer, you get an O(n) time, O(1) space algorithm (the formula is i -> 2*i modulo 2n+1). Refer the above paper for more details.

循环移位数组的问题：循环移位大小为n k个数组也给出了结果数组的一个排列（由公式我去给到I + K模n），并且也可以在线性时间和就地使用以下的循环方法来解决。事实上，在元素交换的数量而言，这下面的循环方法的好的比3逆转算法。当然，以下的循环方法可以杀死，因为访问模式和在实践中的高速缓存中的3反转算法实际上可能有良好表现。

The cyclic shift an array problem: Cyclic shift an array of size n by k also gives a permutation of the resulting array (given by the formula i goes to i+k modulo n), and can also be solved in linear time and in-place using the following the cycle method. In fact, in terms of the number of element exchanges this following cycle method is better than the 3 reverses algorithm. Of course, following the cycle method can kill the cache because of the access patterns and in practice the 3 reverses algorithm might actually fare better.

至于面试，如果面试是一个通情达理的人，他们会看你如何的认为的和处理这个问题，而不是你是否真正解决这个问题。所以，即使你没有解决一个问题，我觉得你不应该气馁。

As for interviews, if the interviewer is a reasonable person, they will be looking at how you think and approach the problem and not whether you actually solve it. So even if you don't solve a problem, I think you should not be discouraged.

这篇关于如何掌握就地阵列修改算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！