Fra*_*ank 25 arrays algorithm in-place
我正准备进行软件工作面试,而且我在就地修改阵列时遇到了麻烦.例如,在out-shuffle问题中,你交错两个数组的一半,这样1 2 3 4 5 6 7 8就会变成1 5 2 6 3 7 4 8. 这个问题要求一个恒定存储器解决方案(和线性) - 时间,虽然我不确定这是否可能).
首先,我认为线性算法是微不足道的,但后来我无法解决它.然后我找到了一个简单的O(n^2)算法,但它花了我很长时间.我仍然没有找到更快的解决方案.
我记得也很难解决Bentley编程珍珠中的类似问题,第2栏:旋转i位置左侧的数组(例如,旋转2的abcde变为cdeab),O(n)并且只有几个字节的额外空间.
有没有人有提示帮助我解决这些问题？是否有针对此类问题的特定教程？谢谢!
小智 15
关于O(n)时间,O(1)空间算法用于out-shuffle
在O(n)时间和O(1)空间中进行彻底改变是可能的,但这很难.不确定为什么人们认为这很容易,并建议你尝试别的东西.
下面的论文有一个O(n)时间和O(1)空间解决方案(虽然它是为了洗牌,但是做洗牌使得混乱变得微不足道):
http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf
关于解决就地阵列修改算法的方法
就地修改算法可能变得非常难以处理.
考虑几个:
对不起,如果这听起来令人沮丧,但没有魔法灵药可以解决所有就地算法问题.您需要处理问题,找出其属性并尝试利用它们(大多数算法就是这种情况).
也就是说,对于导致原始数组排列的数组修改,您可以尝试使用的方法following the cycles of the permutation.基本上任何排列都可以写成一组不相交的循环(参见John的答案).例如排列:
1 4 2 5 3 6
的1 2 3 4 5 6可以写成
1 -> 1
2 -> 3 -> 5 -> 4 -> 2
6 -> 6.
你可以阅读箭头'去'.
因此,1 2 3 4 5 6要按照三个周期来排列数组:
1变为1.
6到6.
2到3,3到5,5到4和4到2.
要遵循这个长周期,您只能使用一个临时变量.将3存储在其中.把2放在3的位置.现在把3分放在5中,然后将5分存储在temp中,依此类推.由于您只使用常量额外临时空间来跟踪特定周期,因此您正在对该周期进行数组的就地修改.
现在,如果我给你一个计算元素所在位置的公式,你现在需要的只是每个周期的起始元素集.
明智地选择循环的起点可以使算法变得容易.如果你想出O(1)空间中的起点,你现在有了一个完整的就地算法.这是您可能必须熟悉问题并利用其属性的地方.
即使您不知道如何计算循环的起点,但有一个公式来计算下一个元素,您可以使用此方法在某些特殊情况下获得O(n)时间就地算法.
例如:如果你知道有符号整数数组只保留正整数.
您现在可以遵循循环,但将其中的数字否定为"已访问"元素的指示.现在,您可以遍历数组并选择您遇到的第一个正数,并按照周期进行操作,使循环元素为负数并继续查找未触及的元素.最后,您只需将所有元素再次设为正,以获得最终的排列.
你得到O(n)时间和O(1)空间算法!当然,我们通过使用数组整数的符号位作为我们的个人"访问"位图来"欺骗".
即使数组不一定是整数,这个方法(遵循循环,而不是符号位的黑客:-))实际上可以用来解决你说的两个问题:
The inshuffle (or out-shuffle) problem:当2n + 1是3的幂时,可以显示(使用数论)1,3,3 ^ 2等处于不同的循环中并且使用这些循环覆盖所有循环.结合这个事实,即洗牌很容易分裂和征服,你得到一个O(n)时间,O(1)空间算法(公式是i - > 2*i模2n + 1).有关详细信息,请参阅上面的文章.
The cyclic shift an array problem:循环移位一个大小为n乘k的数组也给出了结果数组的排列(由公式i给出i + k模n),也可以使用下面的循环在线性时间内就地求解方法.实际上,就元素交换的数量而言,该后续循环方法优于 3反转算法.当然,遵循循环方法可以因为访问模式而终止缓存,并且在实践中,3反转算法实际上可能更好.
至于面试,如果面试官是一个合理的人,他们会看你如何思考和解决问题,而不是你是否真正解决了问题.因此,即使你没有解决问题,我认为你不应该气馁.