约束：
- O（1）空间
- （N）时间
它不是一门功课的问题只是我遇到了一个有趣的问题。
这里有一些解决方案，我能想到的，但没有什么做它在给定的约束。
方法1
*具有O（N）存储器*
- 划分为两个部分递归阵列。 （保持分裂直到大小<= 2对每个子问题）
- 排序每个子问题阵列的第一和数字在端。
- 合并子问题阵列
方法2
在为O（n log n）的时间
- 排序所述阵列基于字典顺序变得1234ABCD
- 反向阵列4321dcba的两半
- 扭转整个字符串ABCD1234
方法3
如果用数字的范围限定在
此外，如果情况是，数字是在特定的范围内，那么我可以初始化INT说轨道= 0; 并设置适当的位，当我在阵列例如遇到一个数字（1 <<一个[2]）。 1.交换字母在轨道可变3.阵列2.标记号码的第一半后使用轨道填补阵列的第二个一半。
方法4，我们可以使用方法3 HashMap的，如果我们要删除的整数的范围有限，但那么它将需要更多的内存。
可没想到更好的办法来解决O（1）时间和O（n）的空间，一般的问题。
这里普遍问题是指：
给定一个序列x1y1x2y2x3y3 .... xnyn其中x1，x2是字母X1 <X2 <... <Xn和Y1Y2 ... yn是整数。 Y1 <Y2 <.... <炔排列的输出作为X1X2 ...... xny1y2 ...炔
有什么建议 ？
什么是n ？ 假设n在输入的大小：
这被称为列表的卷积。 从本质上说，必须转换对的列表(a,1),(b,2),(c,3),(d,4)到一对列表(a,b,c,d),(1,2,3,4) 这是相同的操作作为一个矩阵的转置。
无论如何，你必须考虑该结构的作为k维阵列，其中，k = LGñ。 数组的卷积是你得到什么，当你“移动”的值的索引我的索引我按位旋转。 在这种情况下，我们要旋转的指数向右1位。 这意味着，卷积是与k的最大周期长度的排列。 特技然后从每个周期中选择一个索引 - 这将总是包括0和n-1。
编辑：其实，你可能想要的是置换分解成换位的产物。 然后，所有你需要做的是掉期。
解：
- 首先（索引0）和最后一个（指数n-1）不动。
- 的移动总数为（n - 2）
在源偶数元素是字母。 他们进入上半场。
目标=焦耳/ 2 // n为偶数
在源奇数元素是数字，并且它们移动到第二的一半。
目标= N / 2 +地板（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）的算法。
空隙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);
}
}
