原数组为a1, a2, a3,....an,b1,b2,b3...bn
变换成b1, a1, b2, a2, b3, a3.....bn,an
要求空间复杂度为o(1):
变换成b1, a1, b2, a2, b3, a3.....bn,an
要求空间复杂度为o(1):
分析清楚数组变换前后下标的对应情况即可。需要注意的是这个变换可能是若干个轮换，需要将所有的轮换都恰好处理一次。
算法：
TransformArray(array, n): // n是题目中的n，array的大小是2n1. for s = 0 to n:2. if s 是一个轮换组的第一个元素下标:3. j <- s4. tmp <- array[j]5. do:6. j <- j转换后的下标7. swap(tmp, array[j])8. while j != s
int Trans(int x, int n) ...{
if (x < n) ...{
return (x << 1) + 1; } else ...{ return (x-n) << 1;
}
}bool IsFirstOfAGroup(int s, int n) ...{ int i = s; do ...{ i = Trans(i, n); if (i < s) return false; } while (i != s); return true;}template <typename T>void TransArratStartFrom(vector<T>& array, int s, int n) ...{ T tmp = array[s]; int j = s; do ...{ j = Trans(j, n); swap(array[j], tmp); } while (j != s);}template <typename T>void TransWholeArray(vector<T>& array, int n) ...{ for (int s = 0; s < n; ++s) ...{ if (IsFirstOfAGroup(s, n)) TransArratStartFrom(array, s, n); }}