[转]经典算法之子数组换位问题

陈文浩 18/04/03 22:49:49

子数组换位问题

设a[0:n-1]是一个有n个元素的数组,k(0<=k<=n-1)是一个非负整数。
试设计一个算法将子数组a[0:k]与a[k+1,n-1]换位。要求算法在最坏情况下耗时O(n),且只用到O(1)的辅助空间。

初步思考:最简单的方法就是循环(n-k-1)次,将a数组的末尾数字插入到a[0]之前。

具体做法:
(1) 首先开辟一个额外空间temp用于存放每一次a数组的末尾数据。
(2) temp <- a[n-1]
(3) 将a[0: n-2] 每个数据都依次向后移动一位赋值给a[1: n-1]。
(4) a[0] <- temp
(5) 循环执行(2) -(4) 步 (n-k+1)次。

代价分析: 时间代价—— O((n-1)*(n-k+1)) 即O(n^2)数量级;空间代价: O(1)

我们仔细想想还有没有更快的办法呢?试想一下,如果a[0 : k] 与 a[k+1 : n-1] 正好长度相等,则可以直接一一对应交换即可。 当然,这道题的难点就在于k并不一定是a数组的中间位置。即便如此,但是仍然可以交换:

采用分治算法

当v[k]左边子数组的长度等于右边的子数组长度时,直接将两个子数组对应的元素互换即可
当左边子数组长度小于右边子数组长度时,将左边子数组与右边子数组右边的等长子数组对换,再对结果递归调用对换函数
当右边子数组长度小于左边子数组长度时,将右边子数组与左边子数组左边的等长子数组对换,再对结果递归调用对换函数

通过分析,可知只需要利用保存元素对换时的交换空间即可,空间复杂度为O(1),子数组对换时时间复杂度不会超过O(n)

代码如下:

//交换数组的两段大小相等的范围的对应数据  
//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);  
        }  
    }  

}  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

以下以数组1,2,| 3,4,5,6,7数组中交换1、2和3、4、5、6、7两个数组块为例分析程序运行过程:

初始数组:1,2,| 3,4,5,6,7
此时: low=0 k=1 high=6
执行: patition(a,0,1,6);

左边长度小于右边
执行: swap(a,0,1,5,6), 将1、2和6、7互换 数组变为: 6,7,3,4,5,1、2
此时: low=0 k=1 high=high-(k-low+1)=4
执行: patition(a,0,1,4);

左边长度小于右边
执行: swap(a,0,1,3,4), 将6、7和4、5互换 数组变为: 4,5,3,6,7,1、2
此时: low=0 k=1 high=high-(k-low+1)=2
执行: patition(a,0,1,2);

左边长度大于右边
执行: swap(a,0,0,2,2), 将4和3互换
数组变为: 3,5,4,6,7,1、2
此时: low=1 k=1 high==2
执行: patition(a,1,1,2);

左边长度等于右边
执行: 将4和5互换
数组变为: 3,4,5,6,7,1、2
结束

当然,此处还有另外一种算法:三次反转算法,类似线性代数中的转置的性质,有如下算法:
这里写图片描述

算法复杂性分析:3次反转算法最多用了n次数组单元交换运算,每次交换运算需要3次元素移动。因此最坏情况下用了3n次元素移动,时间复杂性为O(n),空间复杂性为 O(1)。

作者:m0_37787222 发表于 2018/04/03 22:49:49 原文链接 https://blog.csdn.net/m0_37787222/article/details/79810570
阅读:54 评论:2 查看评论