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).
我正在准备一个软件工作面试，我在现场数组修改方面有困难。例如，在出牌问题中，你将一个数组的两个半部分交错，这样，1 2 3 4 5 6 7 8就变成了1 5 2 6 3 7 4 8。这个问题需要一个常量内存解决方案(和线性时间，尽管我不确定这是否可能)。
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.
首先，我认为线性算法是微不足道的，但是我不能算出来。然后我找到了一个简单的O(n ^ 2)算法但我花了很长时间。我还是找不到更快的解。
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.
我还记得在解决Bentley's Programming pearl, columnn 2:旋转I position(例如abcde旋转2变成cdeab)留下的一个数组时遇到过类似的问题。
Does anyone have tips that help wrap my head around such problems? Are there specific tutorials for such questions? Thanks!
有人能帮我解决这些问题吗?是否有针对此类问题的特定教程?谢谢!
7 个解决方案
#1
15
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)空间中进行换位是可能的，但这是困难的。不知道为什么人们认为这很容易，所以建议你试试别的。
The following paper has an O(n) time and O(1) space solution (though it is for inshuffle, but doing inshuffle makes outshuffle trivial):
下一篇论文有O(n)时间O(1)空间解(虽然是inshuffle，但做inshuffle并不重要):
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.
就地修改算法可能变得非常难以处理。
Consider a couple:
考虑几个:
- Inplace out-shuffle in linear time. Uses number theory.
- 线性时间的置换。用数论。
- In-place merge sort, was open for a few years. An algorithm came but was too complicated to be practical. Uses very complicated bookkeeping.
- 就地合并排序，开放了几年。算法来了，但是太复杂了，不实用。使用非常复杂的簿记。
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
of 1 2 3 4 5 6 can be written as
1 2 3 4 5 6可以写成。
1 -> 1
2 -> 3 -> 5 -> 4 -> 2
6 -> 6.
you can read the arrow as 'goes to'.
你可以把箭头读成“走向”。
So to permute the array 1 2 3 4 5 6 you follow the three cycles:
为了排列数组1 2 3 4 5 6你遵循了三个循环
1 goes to 1.
1到1。
6 goes to 6.
6到6。
2 goes to 3, 3 goes to 5, 5 goes to 4 and 4 goes to 2.
2除3 3 3除5 5除4 4除2。
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.
要遵循这个长周期，只需使用一个临时变量。店3。把2放在3所在的位置。现在把3放入5中，把5存储在temp中，以此类推。由于您只使用常数额外的临时空间来跟踪特定的周期，所以您正在对该周期的数组进行就地修改。
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.
现在如果我给你一个计算元素去向的公式，你现在需要的是每个周期的开始元素的集合。
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(1)空间中找到了起点，那么现在您就有了一个完整的就地算法。实际上，您可能需要熟悉这个问题并利用它的特性。
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.
即使您不知道如何计算周期的起始点，但是有一个计算下一个元素的公式，您也可以使用该方法在某些特殊情况下获得O(n)时间就地算法。
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.
您现在可以跟踪这些循环，但将它们中的数字作为“已访问”元素的指示器。现在，您可以遍历数组并选择遇到的第一个正数，并按照循环进行，使循环的元素为负，并继续寻找未被修改的元素。最后你只要让所有的元素都为正就能得到结果的排列。
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.
你得到O(n)时间和O(1)空间算法!当然，我们有点“欺骗”，使用数组整数的符号位作为我们的“访问”位图。
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:
即使数组不一定是整数，这个方法(遵循循环，而不是使用符号位:-)实际上也可以用来解决两个问题:
-
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.inshuffle(或out-shuffle)问题:当2 n + 1 = 3的幂,可以显示(使用数论),1,3,3 ^ 2,等在不同的周期和周期都是使用这些覆盖。结合这个事实，inshuffle很容易被分割和征服，你得到O(n)时间，O(1)空间算法(公式是i -> 2*i modulo 2n+1)。详情请参阅上述文件。
-
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.循环移位阵列问题:循环移位大小为n×k的阵列也给出结果阵列的排列(由公式i代入i+k模n给出)，也可以用下面的循环方法在线性时间和就地解决。事实上，就元素交换的数量而言，下面的循环方法比3逆算法要好。当然，由于访问模式，遵循循环方法可以杀死缓存，实际上，3反向算法可能会更好。
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.
至于面试，如果面试官是个通情达理的人，他们会看你是如何思考和解决问题的，而不是看你是否真的解决了问题。所以即使你不解决问题，我认为你也不应该气馁。
#2
4
The basic strategy with in place algorithms is to figure out the rule for moving a entry from slot N to slot M.
有合适算法的基本策略是找出将条目从槽N移动到槽M的规则。
So, your shuffle, for instance. if A and B are cards and N is the number of chards. the rules for the first half of the deck are different than the rules for the second half of the deck
比如你的洗牌。如果A和B是纸牌，N是chards的数目。前半副牌的规则与后半副牌的规则不同
// A is the current location, B is the new location.
// this math assumes that the first card is card 0
if (A < N/2)
B = A * 2;
else
B = (A - N/2) * 2 + 1;
Now we know the rule, we just have to move each card, each time we move a card, we calculate the new location, then remove the card that is currently in B. place A in slot B, then let B be A, and loop back to the top of the algorithm. Each card moved displaces the new card which becomes the next card to be moved.
现在我们知道规则,我们只需要每个卡片,每次我们移动卡,我们计算新位置,然后把卡目前在槽中放置一个B,然后让B是一个,循环回到顶部的算法。移动的每张卡都替换了新卡，新卡将成为移动的下一张卡。
I think the analysis is easier if we are 0 based rather than 1 based, so
我认为如果我们是0而不是1，那么分析会更简单
0 1 2 3 4 5 6 7 // before
0 4 1 5 2 6 3 7 // after
So we want to move 1->2 2->4 4->1 and that completes a cycle then move 3->6 6->5 5->3 and that completes a cycle and we are done.
所以我们要移动1->2 ->4 ->1这就完成了一个循环然后移动3->6 6->5 ->3这就完成了一个循环，我们做完了。
Now we know that card 0 and card N-1 don't move, so we can ignore those, so we know that we only need to swap N-2 cards in total. The only sticky bit is that there are 2 cycles, 1,2,4,1 and 3,6,5,3. when we get to card 1 the second time, we need to move on to card 3.
现在我们知道牌0和牌N-1不会移动，所以我们可以忽略它们，所以我们知道我们只需要交换N-2张牌。唯一棘手的是有两个周期，1 2 4 1 3 6 5 3。当我们第二次拿到第一张牌时，我们需要换到第三张牌。
int A = 1;
int N = 8;
card ary[N]; // Our array of cards
card a = ary[A];
for (int i = 0; i < N/2; ++i)
{
if (A < N/2)
B = A * 2;
else
B = (A - N/2) * 2 + 1;
card b = ary[B];
ary[B] = a;
a = b;
A = B;
if (A == 1)
{
A = 3;
a = ary[A];
}
}
Now this code only works for the 8 card example, because of that if test that moves us from 1 to 3 when we finish the first cycle. What we really need is a general rule to recognize the end of the cycle, and where to go to start the next one.
这段代码只适用于8张牌的例子，因为当我们完成第一个循环时，如果测试将我们从1移动到3。我们真正需要的是一个通用的规则来识别周期的结束，以及从哪里开始下一个周期。
That rule could be mathematical if you can think of a way, or you could keep track of which places you had visited in a separate array, and when A is back to a visited place, you could then scan forward in your array looking for the first non-visited place.
这条规则可以是数学的，如果你能想到一种方法，或者你可以记录你在一个单独的数组中访问过哪些地方，当a返回到访问过的地方，你就可以在你的数组中向前扫描，寻找第一个没有访问过的地方。
For your in-place algorithm to be 0(n), the solution will need to be mathematical.
要使你的就地算法为0(n)，解必须是数学的。
I hope this breakdown of the thinking process is helpful to you. If I was interviewing you, I would expect to see something like this on the whiteboard.
我希望这个思维过程的分解对你有帮助。如果我面试你，我希望在白板上看到这样的东西。
Note: As Moron points out, this doesn't work for all values of N, it's just an example of the sort of analysis that an interviewer is looking for.
注意:正如Moron指出的，这并不适用于所有的N值，它只是面试官正在寻找的那种分析的一个例子。
#3
1
For the first one, let's assume n is even. You have:
对于第一个，假设n是偶数。你有:
first half: 1 2 3 4
second : 5 6 7 8
上半场:1 2 3 4秒:5 6 7 8
Let x1 = first[1], x2 = second[1].
设x1 =第一[1]，x2 =第二[1]。
Now, you have to print one from first half, one from second, one from first, one from second...
现在，你必须打印一个来自上半场，一个来自第二名，一个来自第一名，一个来自第二名……
Meaning first[1], second[1], first[2], second[2], ...
Obviously you don't keep two halves in memory, as that will be O(n) memory. You keep pointers to the two halves. Do you see how you'd do that?
意思是第一个[1]，第二个[1]，第一个[2]，第二个[2]，…很明显，你没有把两半保留在内存中，因为那将是O(n)内存。你保持指针指向两半。你知道怎么做吗?
The second is a bit harder. Consider: 12345abcde..cde.....ab..cdeabcdeab
第二点有点难。考虑:12345中的. .cde .....ab . .cdeab cdeab
Do you notice anything? You should notice that the question basically asks you to move the first i characters to the end of your string, without affording the luxury of copying the last n - i in a buffer then appending the first i and then returning the buffer. You need to do with O(1) memory.
你注意到什么?您应该注意到，这个问题基本上要求您将第一个i字符移动到字符串的末尾，而无需在缓冲区中复制最后一个n - i，然后附加第一个i，然后返回缓冲区。您需要使用O(1)内存。
To figure how to do this you basically need a lot of practice with these kind of problems, as with anything else. Practice makes perfect basically. If you've never done these kinds of problems before, it's unlikely you'll figure it out. If you have, then you have to think about how you can manipulate the substrings and / or indices such that you solve your problem under the given constraints. The general rule is to work as much as possible and learn as much as possible so you'll figure out solutions to these problems very fast when you see them, but the solution differs quite a bit from problem to problem. There's no clear recipe for success I'm afraid. Just read a lot and understand the stuff you read before you move on.
要想知道如何做到这一点，你需要大量的练习来解决这些问题，就像其他问题一样。熟能生巧。如果你以前从来没有做过这类问题，你不可能解决它。如果有，那么您必须考虑如何操作子字符串和/或索引，以便在给定的约束下解决问题。一般的规则是尽可能多地工作，尽可能多地学习，这样当你看到这些问题时，你就会很快地找到它们的解决方案，但解决方案因问题而异。恐怕没有明确的成功秘诀。在你继续之前，先多读一些，理解一下你读过的东西。
The logic for the second problem is this: what happens if we reverse the substring [1, 2], the substring [3, 5] and then concatenate them and reverse that? We have, in general:
第二个问题的逻辑是:如果我们反转子字符串[1,2]，子字符串[3,5]，然后将它们串联起来，然后反转，会发生什么?我们有,一般来说:
1, 2, 3, 4, ..., i, i + 1, i + 2, ..., N
reverse [1, i] =>i, i - 1, ..., 4, 3, 2, 1, i + 1, i + 2, ..., N
reverse [i + 1, N] =>i, i - 1, ..., 4, 3, 2, 1, N, ..., i + 1
reverse [1, N] =>i + 1, ..., N, 1, 2, 3, 4, ..., i - 1, i
, which is what you wanted. Writing the reverse function using O(1) memory should be trivial.
1、2、3、4、……， i, i + 1, i + 2，…， N反向[1,i] => i, i - 1，…， 4 3 2 1 i + 1 i + 2…， N反向[i + 1, N] => i, i - 1，…， 4,3,2,1,n，……， i + 1反向[1,N] => i + 1，…，N, 1 2 3 4，…i - 1 i，这就是你想要的。使用O(1)内存编写反向函数应该很简单。
#4
1
Frank,
弗兰克,
For programming with loops and arrays, nothing beats David Gries's textbook The Science of Programming. I studied it over 20 years ago, and there are ideas that I still use every day. It is very mathematical and will require real effort to master, but that effort will repay you many times over for your whole career.
对于用循环和数组进行编程，没有什么能比David Gries的教科书《编程科学》更好的了。我在20多年前就开始研究它了，还有一些我每天都在使用的想法。这是非常数学化的，需要真正的努力去掌握，但是这种努力将会在你的整个职业生涯中回报你很多次。
#5
0
Generally speaking, the idea is to loop through the array once, while
一般来说，我们的想法是在数组中循环一次
- storing the value at the position you are at in a temporary variable
- 将值存储在一个临时变量中。
- finding the correct value for that position and writing it
- 找到这个位置的正确值并将其写下来
- either move on to the next value, or figure out what to do with your temporary value before continuing.
- 要么转移到下一个值，要么在继续之前弄清楚如何处理临时值。
#6
0
Complementing Aryabhatta's answer:
补充阿雅巴塔的回答是:
There is a general method to "follow the cycles" even without knowing the starting positions for each cycle or using memory to know visited cycles. This is specially useful if you need O(1) memory.
有一种通用的方法可以“跟踪周期”，即使不知道每个周期的起始位置或使用内存知道已访问的周期。如果您需要O(1)内存，这是特别有用的。
For each position i in the array, follow the cycle without moving any data yet, until you reach...
对于数组中的每个位置i，遵循循环，但不移动任何数据，直到到达……
- the starting position i: end of the cyle. this is a new cycle: follow it again moving the data this time.
- 起始位置i: cyle的末端。这是一个新的循环:再次跟随它移动数据。
- a position lower than i: this cycle was already visited, nothing to do with it.
- 低于i的位置:这个循环已经被访问了，与它无关。
Of course this has a time overhead (O(n^2), I believe) and has the cache problems of the general "following cycles" method.
当然,这有一个时间开销(O(n ^ 2),我相信),缓存一般“后周期”方法的问题。
#7
0
A general approach could be as follows:
一般办法如下:
- Construct a positions array int[] pos, such that pos[i] refers to the position (index) of a[i] in the shuffled array.
- 构造一个位置数组int[] pos，以便pos[i]引用改组后的数组中的[i]的位置(索引)。
-
Rearrange the original array int[] a, according to this positions array pos.
根据这个位置重新排列原数组int[] a。
/** Shuffle the array a. */ void shuffle(int[] a) { // Step 1 int [] pos = contructRearrangementArray(a) // Step 2 rearrange(a, pos); } /** * Rearrange the given array a according to the positions array pos. */ private static void rearrange(int[] a, int[] pos) { // By definition 'pos' should not contain any duplicates, otherwise rearrange() can run forever. // Do the above sanity check. for (int i = 0; i < pos.length; i++) { while (i != pos[i]) { // This while loop completes one cycle in the array swap(a, i, pos[i]); swap(pos, i, pos[i]); } } } /** Swap ith element in a with jth element. */ public static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }
As an example, for the case of outShuffle the following would be an implementation of contructRearrangementArray().
例如，对于outShuffle的情况，下面是contructRearrangementArray()的实现。
/**
* array : 1 2 3 4 5 6 7 8
* pos : 0 2 4 6 1 3 5 7
* outshuffle: 1 5 2 6 3 7 4 8 (outer boundaries remain same)
*/
public int[] contructRearrangementArray(int[] a)
{
if (a.length % 2 != 0) {
throw new IllegalArgumentException("Cannot outshuffle odd sized array");
}
int[] pos = new int[a.length];
for (int i = 0; i < pos.length; i++) {
pos[i] = i * 2 % (pos.length - 1);
}
pos[a.length - 1] = a.length - 1;
return pos;
}
#1
15
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)空间中进行换位是可能的，但这是困难的。不知道为什么人们认为这很容易，所以建议你试试别的。
The following paper has an O(n) time and O(1) space solution (though it is for inshuffle, but doing inshuffle makes outshuffle trivial):
下一篇论文有O(n)时间O(1)空间解(虽然是inshuffle，但做inshuffle并不重要):
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.
就地修改算法可能变得非常难以处理。
Consider a couple:
考虑几个:
- Inplace out-shuffle in linear time. Uses number theory.
- 线性时间的置换。用数论。
- In-place merge sort, was open for a few years. An algorithm came but was too complicated to be practical. Uses very complicated bookkeeping.
- 就地合并排序，开放了几年。算法来了，但是太复杂了，不实用。使用非常复杂的簿记。
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
of 1 2 3 4 5 6 can be written as
1 2 3 4 5 6可以写成。
1 -> 1
2 -> 3 -> 5 -> 4 -> 2
6 -> 6.
you can read the arrow as 'goes to'.
你可以把箭头读成“走向”。
So to permute the array 1 2 3 4 5 6 you follow the three cycles:
为了排列数组1 2 3 4 5 6你遵循了三个循环
1 goes to 1.
1到1。
6 goes to 6.
6到6。
2 goes to 3, 3 goes to 5, 5 goes to 4 and 4 goes to 2.
2除3 3 3除5 5除4 4除2。
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.
要遵循这个长周期，只需使用一个临时变量。店3。把2放在3所在的位置。现在把3放入5中，把5存储在temp中，以此类推。由于您只使用常数额外的临时空间来跟踪特定的周期，所以您正在对该周期的数组进行就地修改。
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.
现在如果我给你一个计算元素去向的公式，你现在需要的是每个周期的开始元素的集合。
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(1)空间中找到了起点，那么现在您就有了一个完整的就地算法。实际上，您可能需要熟悉这个问题并利用它的特性。
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.
即使您不知道如何计算周期的起始点，但是有一个计算下一个元素的公式，您也可以使用该方法在某些特殊情况下获得O(n)时间就地算法。
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.
您现在可以跟踪这些循环，但将它们中的数字作为“已访问”元素的指示器。现在，您可以遍历数组并选择遇到的第一个正数，并按照循环进行，使循环的元素为负，并继续寻找未被修改的元素。最后你只要让所有的元素都为正就能得到结果的排列。
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.
你得到O(n)时间和O(1)空间算法!当然，我们有点“欺骗”，使用数组整数的符号位作为我们的“访问”位图。
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:
即使数组不一定是整数，这个方法(遵循循环，而不是使用符号位:-)实际上也可以用来解决两个问题:
-
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.inshuffle(或out-shuffle)问题:当2 n + 1 = 3的幂,可以显示(使用数论),1,3,3 ^ 2,等在不同的周期和周期都是使用这些覆盖。结合这个事实，inshuffle很容易被分割和征服，你得到O(n)时间，O(1)空间算法(公式是i -> 2*i modulo 2n+1)。详情请参阅上述文件。
-
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.循环移位阵列问题:循环移位大小为n×k的阵列也给出结果阵列的排列(由公式i代入i+k模n给出)，也可以用下面的循环方法在线性时间和就地解决。事实上，就元素交换的数量而言，下面的循环方法比3逆算法要好。当然，由于访问模式，遵循循环方法可以杀死缓存，实际上，3反向算法可能会更好。
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.
至于面试，如果面试官是个通情达理的人，他们会看你是如何思考和解决问题的，而不是看你是否真的解决了问题。所以即使你不解决问题，我认为你也不应该气馁。
#2
4
The basic strategy with in place algorithms is to figure out the rule for moving a entry from slot N to slot M.
有合适算法的基本策略是找出将条目从槽N移动到槽M的规则。
So, your shuffle, for instance. if A and B are cards and N is the number of chards. the rules for the first half of the deck are different than the rules for the second half of the deck
比如你的洗牌。如果A和B是纸牌，N是chards的数目。前半副牌的规则与后半副牌的规则不同
// A is the current location, B is the new location.
// this math assumes that the first card is card 0
if (A < N/2)
B = A * 2;
else
B = (A - N/2) * 2 + 1;
Now we know the rule, we just have to move each card, each time we move a card, we calculate the new location, then remove the card that is currently in B. place A in slot B, then let B be A, and loop back to the top of the algorithm. Each card moved displaces the new card which becomes the next card to be moved.
现在我们知道规则,我们只需要每个卡片,每次我们移动卡,我们计算新位置,然后把卡目前在槽中放置一个B,然后让B是一个,循环回到顶部的算法。移动的每张卡都替换了新卡，新卡将成为移动的下一张卡。
I think the analysis is easier if we are 0 based rather than 1 based, so
我认为如果我们是0而不是1，那么分析会更简单
0 1 2 3 4 5 6 7 // before
0 4 1 5 2 6 3 7 // after
So we want to move 1->2 2->4 4->1 and that completes a cycle then move 3->6 6->5 5->3 and that completes a cycle and we are done.
所以我们要移动1->2 ->4 ->1这就完成了一个循环然后移动3->6 6->5 ->3这就完成了一个循环，我们做完了。
Now we know that card 0 and card N-1 don't move, so we can ignore those, so we know that we only need to swap N-2 cards in total. The only sticky bit is that there are 2 cycles, 1,2,4,1 and 3,6,5,3. when we get to card 1 the second time, we need to move on to card 3.
现在我们知道牌0和牌N-1不会移动，所以我们可以忽略它们，所以我们知道我们只需要交换N-2张牌。唯一棘手的是有两个周期，1 2 4 1 3 6 5 3。当我们第二次拿到第一张牌时，我们需要换到第三张牌。
int A = 1;
int N = 8;
card ary[N]; // Our array of cards
card a = ary[A];
for (int i = 0; i < N/2; ++i)
{
if (A < N/2)
B = A * 2;
else
B = (A - N/2) * 2 + 1;
card b = ary[B];
ary[B] = a;
a = b;
A = B;
if (A == 1)
{
A = 3;
a = ary[A];
}
}
Now this code only works for the 8 card example, because of that if test that moves us from 1 to 3 when we finish the first cycle. What we really need is a general rule to recognize the end of the cycle, and where to go to start the next one.
这段代码只适用于8张牌的例子，因为当我们完成第一个循环时，如果测试将我们从1移动到3。我们真正需要的是一个通用的规则来识别周期的结束，以及从哪里开始下一个周期。
That rule could be mathematical if you can think of a way, or you could keep track of which places you had visited in a separate array, and when A is back to a visited place, you could then scan forward in your array looking for the first non-visited place.
这条规则可以是数学的，如果你能想到一种方法，或者你可以记录你在一个单独的数组中访问过哪些地方，当a返回到访问过的地方，你就可以在你的数组中向前扫描，寻找第一个没有访问过的地方。
For your in-place algorithm to be 0(n), the solution will need to be mathematical.
要使你的就地算法为0(n)，解必须是数学的。
I hope this breakdown of the thinking process is helpful to you. If I was interviewing you, I would expect to see something like this on the whiteboard.
我希望这个思维过程的分解对你有帮助。如果我面试你，我希望在白板上看到这样的东西。
Note: As Moron points out, this doesn't work for all values of N, it's just an example of the sort of analysis that an interviewer is looking for.
注意:正如Moron指出的，这并不适用于所有的N值，它只是面试官正在寻找的那种分析的一个例子。
#3
1
For the first one, let's assume n is even. You have:
对于第一个，假设n是偶数。你有:
first half: 1 2 3 4
second : 5 6 7 8
上半场:1 2 3 4秒:5 6 7 8
Let x1 = first[1], x2 = second[1].
设x1 =第一[1]，x2 =第二[1]。
Now, you have to print one from first half, one from second, one from first, one from second...
现在，你必须打印一个来自上半场，一个来自第二名，一个来自第一名，一个来自第二名……
Meaning first[1], second[1], first[2], second[2], ...
Obviously you don't keep two halves in memory, as that will be O(n) memory. You keep pointers to the two halves. Do you see how you'd do that?
意思是第一个[1]，第二个[1]，第一个[2]，第二个[2]，…很明显，你没有把两半保留在内存中，因为那将是O(n)内存。你保持指针指向两半。你知道怎么做吗?
The second is a bit harder. Consider: 12345abcde..cde.....ab..cdeabcdeab
第二点有点难。考虑:12345中的. .cde .....ab . .cdeab cdeab
Do you notice anything? You should notice that the question basically asks you to move the first i characters to the end of your string, without affording the luxury of copying the last n - i in a buffer then appending the first i and then returning the buffer. You need to do with O(1) memory.
你注意到什么?您应该注意到，这个问题基本上要求您将第一个i字符移动到字符串的末尾，而无需在缓冲区中复制最后一个n - i，然后附加第一个i，然后返回缓冲区。您需要使用O(1)内存。
To figure how to do this you basically need a lot of practice with these kind of problems, as with anything else. Practice makes perfect basically. If you've never done these kinds of problems before, it's unlikely you'll figure it out. If you have, then you have to think about how you can manipulate the substrings and / or indices such that you solve your problem under the given constraints. The general rule is to work as much as possible and learn as much as possible so you'll figure out solutions to these problems very fast when you see them, but the solution differs quite a bit from problem to problem. There's no clear recipe for success I'm afraid. Just read a lot and understand the stuff you read before you move on.
要想知道如何做到这一点，你需要大量的练习来解决这些问题，就像其他问题一样。熟能生巧。如果你以前从来没有做过这类问题，你不可能解决它。如果有，那么您必须考虑如何操作子字符串和/或索引，以便在给定的约束下解决问题。一般的规则是尽可能多地工作，尽可能多地学习，这样当你看到这些问题时，你就会很快地找到它们的解决方案，但解决方案因问题而异。恐怕没有明确的成功秘诀。在你继续之前，先多读一些，理解一下你读过的东西。
The logic for the second problem is this: what happens if we reverse the substring [1, 2], the substring [3, 5] and then concatenate them and reverse that? We have, in general:
第二个问题的逻辑是:如果我们反转子字符串[1,2]，子字符串[3,5]，然后将它们串联起来，然后反转，会发生什么?我们有,一般来说:
1, 2, 3, 4, ..., i, i + 1, i + 2, ..., N
reverse [1, i] =>i, i - 1, ..., 4, 3, 2, 1, i + 1, i + 2, ..., N
reverse [i + 1, N] =>i, i - 1, ..., 4, 3, 2, 1, N, ..., i + 1
reverse [1, N] =>i + 1, ..., N, 1, 2, 3, 4, ..., i - 1, i
, which is what you wanted. Writing the reverse function using O(1) memory should be trivial.
1、2、3、4、……， i, i + 1, i + 2，…， N反向[1,i] => i, i - 1，…， 4 3 2 1 i + 1 i + 2…， N反向[i + 1, N] => i, i - 1，…， 4,3,2,1,n，……， i + 1反向[1,N] => i + 1，…，N, 1 2 3 4，…i - 1 i，这就是你想要的。使用O(1)内存编写反向函数应该很简单。
#4
1
Frank,
弗兰克,
For programming with loops and arrays, nothing beats David Gries's textbook The Science of Programming. I studied it over 20 years ago, and there are ideas that I still use every day. It is very mathematical and will require real effort to master, but that effort will repay you many times over for your whole career.
对于用循环和数组进行编程，没有什么能比David Gries的教科书《编程科学》更好的了。我在20多年前就开始研究它了，还有一些我每天都在使用的想法。这是非常数学化的，需要真正的努力去掌握，但是这种努力将会在你的整个职业生涯中回报你很多次。
#5
0
Generally speaking, the idea is to loop through the array once, while
一般来说，我们的想法是在数组中循环一次
- storing the value at the position you are at in a temporary variable
- 将值存储在一个临时变量中。
- finding the correct value for that position and writing it
- 找到这个位置的正确值并将其写下来
- either move on to the next value, or figure out what to do with your temporary value before continuing.
- 要么转移到下一个值，要么在继续之前弄清楚如何处理临时值。
#6
0
Complementing Aryabhatta's answer:
补充阿雅巴塔的回答是:
There is a general method to "follow the cycles" even without knowing the starting positions for each cycle or using memory to know visited cycles. This is specially useful if you need O(1) memory.
有一种通用的方法可以“跟踪周期”，即使不知道每个周期的起始位置或使用内存知道已访问的周期。如果您需要O(1)内存，这是特别有用的。
For each position i in the array, follow the cycle without moving any data yet, until you reach...
对于数组中的每个位置i，遵循循环，但不移动任何数据，直到到达……
- the starting position i: end of the cyle. this is a new cycle: follow it again moving the data this time.
- 起始位置i: cyle的末端。这是一个新的循环:再次跟随它移动数据。
- a position lower than i: this cycle was already visited, nothing to do with it.
- 低于i的位置:这个循环已经被访问了，与它无关。
Of course this has a time overhead (O(n^2), I believe) and has the cache problems of the general "following cycles" method.
当然,这有一个时间开销(O(n ^ 2),我相信),缓存一般“后周期”方法的问题。
#7
0
A general approach could be as follows:
一般办法如下:
- Construct a positions array int[] pos, such that pos[i] refers to the position (index) of a[i] in the shuffled array.
- 构造一个位置数组int[] pos，以便pos[i]引用改组后的数组中的[i]的位置(索引)。
-
Rearrange the original array int[] a, according to this positions array pos.
根据这个位置重新排列原数组int[] a。
/** Shuffle the array a. */ void shuffle(int[] a) { // Step 1 int [] pos = contructRearrangementArray(a) // Step 2 rearrange(a, pos); } /** * Rearrange the given array a according to the positions array pos. */ private static void rearrange(int[] a, int[] pos) { // By definition 'pos' should not contain any duplicates, otherwise rearrange() can run forever. // Do the above sanity check. for (int i = 0; i < pos.length; i++) { while (i != pos[i]) { // This while loop completes one cycle in the array swap(a, i, pos[i]); swap(pos, i, pos[i]); } } } /** Swap ith element in a with jth element. */ public static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }
As an example, for the case of outShuffle the following would be an implementation of contructRearrangementArray().
例如，对于outShuffle的情况，下面是contructRearrangementArray()的实现。
/**
* array : 1 2 3 4 5 6 7 8
* pos : 0 2 4 6 1 3 5 7
* outshuffle: 1 5 2 6 3 7 4 8 (outer boundaries remain same)
*/
public int[] contructRearrangementArray(int[] a)
{
if (a.length % 2 != 0) {
throw new IllegalArgumentException("Cannot outshuffle odd sized array");
}
int[] pos = new int[a.length];
for (int i = 0; i < pos.length; i++) {
pos[i] = i * 2 % (pos.length - 1);
}
pos[a.length - 1] = a.length - 1;
return pos;
}