给定一个数组
[a1 a2 a3 ... an b1 b2 b3 ... bn c1 c2 c3 ...cn]
如果不使用额外的内存,你如何重新排序成一个数组
[a1 b1 c1 a2 b2 c2 a3 b3 c3 ... an bn cn]
Jos*_*aum 11
您的问题也可以改为"如何进行就地矩阵换位？".要了解原因,请假设在两个数组中的每个子序列之后添加换行符.这将把第一个数组转换为NxM矩阵,将第二个数组转换为MxN矩阵.
尽管如此,非方形矩阵并非易事.有关问题及其解决方案的全面描述,请参阅就地矩阵转置的维基百科页面.
小智 6
假设您的意思是O(1)内存(或取决于模型O(log n))而不是没有额外的内存,则存在线性时间就地算法.
本文:http://arxiv.org/abs/0805.1598具有针对此案例的算法
a1 ... an b1 ... bn 并希望转换为
b1 a1 b2 a2 ... bn an.
本文还提到你可以将其推广到其他k-way shuffle.在你的情况下,k = 3.
本文中的算法将给出以下内容:
开始a1 a2 ... an b1 b2 ... bn c1 c2 ... cn并转换为
c1 b1 a1 c2 b2 a2 ... cn bn an
另一个通过这个,你可以很容易地得到a1 b1 c2 a2 b2 c2 ... an bn cn.
现在为了概括本文中的算法,我们需要选择素数p,使得k是p ^ 2的原始根.
对于k = 3,p = 5就可以了.
现在要应用算法,首先需要找到最大的m <n这样的3m + 1是5的幂.
注意:这只会在3m + 1是5的偶数幂时发生.因此,当你试图找到m时,你实际上可以使用25的幂.(5 ^奇数 - 1不能被3整除).
一找到m,
你将阵列洗牌
[a1 a2 ... am b1 b2 ... bm c1 c2 ... cm] [a(m+1) ... an b(m+1) ... bn c(m+1) ... cn]
然后使用循环方法(参考论文)获得前3m元素,使用5的幂(包括1 = 5 ^ 0)作为不同循环的起点)并对其余部分进行尾递归.
现在转换
a1 a2 ... an b1 b2 ... bn c1 c2 ... cn
至
[a1 a2 ... am b1 b2 ... bm c1 c2 ... cm] [a(m+1) ... an b(m+1) ... bn c(m+1) ... cn]
你先做一个循环转换
a1 a2 ... am [b1 b2 bm a(m+1) .. an] b(m+1) .. bn c1 c2 ... cn
(方括号中的元素是被移位的元素)
然后进行循环移位
a1 a2 ... am b1 b2 bm a(m+1) .. an [c1 c2 ..cm b(m+1) .. bn ] c(m+1) ... cn
然后最后转移到
a1 a2 ... am b1 b2 bm [c1 c2 ..cm a(m+1) .. an ] b(m+1) .. bn c(m+1) ... cn
注意,循环移位可以在O(n)时间和O(1)空间中完成.
因此整个算法是O(n)时间和O(1)空间.