题目：输入数组：{a1,a2,…,an,b1,b2,…,bn}, 在O(n)的时间,O(1)的空间将这个数组的顺序变为{a1,b1,a2,b2,a3,b3,…,an,bn}， 且不需要移动，通过交换完成，只需一个交换空间。
解答：从结果入手，结果数组的中垂线两边分别a数组的一半和b数组的一半的混合，继续将子数组以中垂线划分下去，可以看到类似的规律，因此，可以使用类似的分治算法实现。
参考代码：
- void solve(int arr[],int s ,int e)
- {
- if( s >= e)
- return;
- int center = (s+e)/2;
- //left part: s,...,center;
- //right part center+1,...,e
- int ls = s;
- int le = center;
- int rs = center+1;
- int re = e;
- for(int i=(le+ls)/2+1,j = rs ; i <= le; i++,j++)
- mySwap(arr[i],arr[j]);
- //奇数个
- if(le!=ls && (le-ls)%2==0){
- le++;
- rs--;
- }
- solve(arr,ls,le);
- solve(arr,rs,re);
- }
网络转载请注明：转载自程序员面试之家
并注明本文链接地址: 谷歌面试题:数组元素移动交叉