给定一个数组[a1b2c3d4]转换为[abcd1234]

Question

制约因素:

1. O(1)空间
2. 准时

这不是一个家庭作业问题,只是我遇到的一个有趣的问题.

以下是我能想到的一些解决方案,但在给定的约束条件下没有任何解决方案.

方法1

*带O(n)内存*

• 递归地将数组分成两部分.(对于每个子问题,继续划分直到<= 2的大小)
• 首先用数组排序每个子问题,在结尾排序数字.
• 合并子问题数组

方法2

在O(n log n)时间内

• 将基于数组的排序顺序排序为1234abcd
• 反转阵列4321dcba的两半
• 反转整个字符串abcd1234

方法3

如果定义了数字范围

如果情况是数字在特定范围内,那么我可以初始化一个int说track = 0; 当我遇到数组中的数字时设置适当的位,例如(1 << a [2]).1.将字母交换到数组2的前半部分.在轨道变量3中标记数字.稍后使用轨道填充数组的后半部分.

方法4 如果我们想要删除整数范围的约束但是它需要更多的内存,我们可以将方法3与HashMap一起使用.

想不出更好的方法来解决O(1)时间和O(n)空间中的泛型问题.

这里的一般问题是指:

给定序列x1y1x2y2x3y3 .... xnyn其中x1,x2是字母x1 <x2 <.... <xn和y1y2 ... yn是整数.y1 <y2 <.... <yn将输出排列为x1x2 ... xny1y2 ... yn

有什么建议 ？

Answer 1

什么是n？假设这n是输入的大小:

这称为列表的卷积.实质上,您必须将对列表转换(a,1),(b,2),(c,3),(d,4)为一对列表(a,b,c,d),(1,2,3,4).它与矩阵的转置操作相同.

无论如何,您必须将结构视为k维数组,其中k = lg n.当你在索引i"移动"索引i按位旋转时,你得到的数组的卷积.在这种情况下,我们希望将索引向右旋转1位.这意味着卷积是一个最大周期长度为k的置换.然后诀窍是从每个循环中选择一个索引 - 这将始终包括0和n-1.

编辑:实际上,你可能想要的是将置换分解为换位的产物.然后,您需要做的就是交换.