首页 > 代码库 > 子数组换位问题

子数组换位问题

 

 

 

问题描述:

设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, a9a0, 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;}

 

子数组换位问题