子数组换位问题
设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数组的中间位置。即便如此,但是仍然可以交换:
如果a[0 : k].length< a[k+1 : n-1].length, 则可以将a[0 : k] 与 a[k+1 : n-1] 中最后一部分大小相同的数据交换:
|-------- a[k+1 : n-1] -----------|
a[0:k]
a[k+1 : n-k-2] a[n-k-1 : n-1]
其中 a[0:k] 与 a[n-k-1 : n-1] 长度相同,因此完全可以一一对应交换成:
|------
a[0 : n-k-2] -------|
a[0:k]
a[k+1 : n-k-2]
a[n-k-1 : n-1]
交换完成以后,则a[n-k-1 : n-1] 已经交换到位,而a[0 :
n-k-2
]还需要进一步这样递归交换。
源代码如下:
#include<stdio.h>
//交换数组的两段大小相等的范围的对应数据
//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 a[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13};
patition(a,0,4,13);
for(int i=0;i<14;i++){
printf("%d ",a[i]);
}
return 0;
}
这样的时间复杂度为O(n),而且交换数据的时候只需要O(1)的额外空间。
分享到:
相关推荐
算法设计与分析(王晓东版)2-11题:将数组的子数组a[0:k]和a[k+1:n-1]进行换位,要求最坏情况下时间复杂度为O(n)
<script type = "text/javascript" src = "../ext-3.3.0/adapter/ext/ext-base.js"></script> <script type = "text/javascript" src = "../ext-3.3.0/ext-all.js"></script> <script type = "text/javascript" ...
组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法
根据青蛙换位游戏,使用回溯法编程实现算法解决换位问题。C++实现。是算法课的一个作业
试设计一个算法将子数组a[0:k]与a[k+1,n-1]换位。要求算法在最坏情况下耗时O(n),且只用到O(1)的辅助空间。 2.在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并...
根据青蛙换位游戏,利用回溯法编程实现换位问题
./cipher <CIPHER> <KEY> <ENC> <INPUTFILE> <OUTPUT> 密码名称: PLF-Playfair RTS-行换位 RFC-围栏 VIG-维格纳尔 CES-凯撒 密钥:要使用的加密密钥。 ENC / DEC:分别加密还是解密。 输入文件:从中读取输入...
青蛙换位问题,包含实验报告.有txt文件输出其换位过程.算法是采用回溯法
为处理等球Packing问题, 在基本拟物算法的基础上设计了序列对称换位策略, 形成了一个启发式的序列对称换位算法。在球形容器内装填1~50个等球时, 此算法改进了其中45项当前记录。特别地, 此算法成功将68个半径为1的等...
用Java图形用户界面实现的“换位密码算法的加密和解密”算法
JAVA换位密码算法,包括加密,解密。用JSP网页做的界面,可以进行对文字的加密(根据密钥)
全排列的几种不同算法,方便快捷的实现求全排列。思路简单清晰
oid jiami(); //加密函数 void jiemi(); //解密函数 //加密函数 void jiami() { ///输入明文字符串 int i=0,l,c,a;...printf("\n输入要加密的明文:");...l<=(a+1)*6;l++) { in[l]=' '; } /////加密过程
主要介绍了python 换位密码算法的实例详解的相关资料,换位密码基本原理:先把明文按照固定长度进行分组,然后对每一组的字符进行换位操作,从而实现加密,需要的朋友可以参考下
“google面试题目——奇偶换位”完全解析。 详细的算法说明、源程序及各个算法比较。 题目: 输入a_1, a_2, ..., a_n, b_1, b_2, ..., b_n,如何在O(n)的时间,用O(1)的空间,将这个序列顺序改为a_1, b_1, ..., a_n...
可拖动换位的照片墙,采用html,css,js编写,实现拖动换位效果
置换算法C语言实现
make_shared是⼀个泛型,<>⾥⾯为数据类型,()对应着new()⾥的东西,其返回值是⼀个shared_ptr类型的变量。 定制删除器 shared_ptr的构造函数可有多个参数,其中有⼀个是shared_ptr(Y *p,D d),第⼀个参数是要...
今天小编就为大家分享一篇python实现换位加密算法的示例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
行业资料-电子功用-换位控制无电感电源插座