首页 > 代码库 > 子数组换位问题
子数组换位问题
问题描述:
设a[0:n-1]是一个有n个元素的数组,k(0<=k<=n-1)是一个非负整数。 试设计一个算法将子数组a[0:k]与a[k+1,n-1]换位。
PS:要求算法在最坏情况下耗时O(n),且只用到O(1)的辅助空间。
例如,数组 {a0, a1, a2, a3, a4, a5, a6, a7, a8, a9},
1、若k=4(两个子数组等长),即需要将数组变成:{a5, a6, a7, a8, a9, a0, a1, a2, a3, a4},两个子数组的长度一样,直接两两交换a[i]与a[i+k]即可;
2、若k=1(后面的子数组更长),即需要将数组变成:{a2, a3, a4, a5, a6, a7, a8, a9, a0, a1},可以先把第一个子数组交换到整个数组的最后,得到:
{a8, a9, a2, a3, a4, a5, a6, a7, a0, a1},然后对前面的子数组再交换一次,得到:
{a2, a3, a4, a5, a6, a7, a8, a9, a0, a1}
3、若k=6(前面的子数组更长),即需要将数组变成:{a8, a9, a0, a1, a2, a3, a4, a5, a6, a7},可以先把第二个子数组交换到整个数组的前面,得到:
{a8, a9, a2, a3, a4, a5, a6, a7, a0, a1},然后问题就变成了怎么把{a2, a3, a4, a5, a6, a7}与{a0, a1}交换了,递归处理即可。
//交换数组的两段大小相等的范围的对应数据//a[low1] <->a[low2] a[low1+1]<->a[low2+1] ... a[high1] <-> a[high2]void swap(int a[],int low1,int high1,int low2,int high2){ int temp; while (low1 <= high1) { temp = a[low1]; a[low1] = a[low2]; a[low2] = temp; low1++; low2++; } }//利用分治算法, 每次选择最小的数组进行换位void patition(int a[], int low, int k, int high){ if (low < high) { if ((k-low+1) == (high-k)) { swap(a,low,k,k+1,high); } else if ((k-low+1)<(high-k)){ swap(a,low,k,low+high-k,high); patition(a,low,k,low+high-k-1); } else { swap(a,low,high+low-k-1,k+1,high); patition(a,high+low-k,k,high); } } }//测试int main(){ int i; int a[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13}; patition(a, 0, 4, 13); for (i=0; i<14; i++) { printf("%d ",a[i]); } printf("\n"); return 0;}
子数组换位问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。