给定一个数组转换为
制约因素：
- O（1）空间
- 准时
这不是一个家庭作业问题，只是我遇到的一个有趣的问题。
以下是我能想到的一些解决方案，但在给定的约束下没有任何解决方案。
方法1
*带O（n）内存*
- 递归地将数组分成两部分。 （对于每个子问题，继续划分直到<= 2的大小）
- 首先使用数组和结尾处的数字对每个子问题进行排序。
- 合并子问题数组
方法2
在O（n log n）时间内
- 将基于数组的排序顺序排序为1234abcd
- 反转arrays4321dcba的两半
- 反转整个字符串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
有什么建议么 ？
什么是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。
编辑：实际上，你可能想要的是将置换分解为换位的产物。 然后，您需要做的就是交换。
解：
- 第一个（索引0）和最后一个（索引n-1）不移动。
- 移动总数为（n – 2）
-
源中的偶数元素都是字母表。 他们进入上半场。
target = j / 2 // n是偶数
-
源中的奇数元素是数字，它们进入后半部分。
target = n / 2 + floor（j / 2）
-
从第1个元素开始，将其移动到目标位置。
- 将您在目标位置找到的内容移动到目标位置，依此类推，直到形成循环。 注1：有时，循环不包括列表中的所有元素，因此，继续j + 2注2：有时，在一个循环结束时，将实现所需的解决方案，但如果我们继续，则数组会再次被打乱。 要解决此问题，请计算发生的移动次数，并在达到n – 2时进行切割。
您可以尝试运行代码，克隆和编辑在线Java编译器IDE
int maxShifts = n - 2; // This is required to fix going around and messing up. int shifts = 0; for (int i = 1; i < n && shifts < maxShifts; i+=2) { int source = i; char itemToMove = array[source]; do { int target; if (source % 2 == 0) { target = source / 2; // Even index is an alphabet } else { target = n/2 + source/2; // Odd index is a digit, that goes in the second half } char tmp = array[target]; array[target] = itemToMove; itemToMove = tmp; shifts++; source = target; } while (i != source /*&& shifts < maxShifts*/); // Full cycle reached }
或者，您可以使用强大的Python，并将其转换为java：
a = [1,'a',2,'b',3,'c',4,'d'] a = a[0:len(a):2] + a[1:len(a):2] print(a) #this will print [1,2,3,4,'a','b','c','d']
这是我在O（n）中的算法。
void cycle_leader（int * arr，int n）{
for (int i = 1; i < n / 2; i+= 2) { int j = i; int save; int tmp = arr[i]; do{ if (j & 1) //odd index element j = n / 2 + j / 2; else j = j / 2; save = arr[j]; arr[j] = tmp; tmp = save; } while(j != i); }
}