`

<算法书>子数组换位问题

阅读更多

子数组换位问题

 

      设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)的额外空间。

分享到:
评论
1 楼 blackdog1987 2012-08-16  
其实思想非常简单。。
就是一个数学公式

注: R代表转置


(aRbR)R  =  ba
根据公式可以推出更复杂的

相关推荐

    Java实现将数组的子数组a[0:k]和a[k+1:n-1]进行换位的算法

    // 定义双指针,i指向子数组a[0:k]的末尾,j指向子数组a[k+1:n-1]的起始 int i = k, j = array.length - 1; // 当i小于j时,继续交换元素 while (i &lt; j) { // 交换a[i]和a[j] int temp = array[i]; array[i]...

    仿支付宝菜单

    &lt;li&gt;&lt;a href="#"&gt;子菜单1&lt;/a&gt;&lt;/li&gt; &lt;li&gt;&lt;a href="#"&gt;子菜单2&lt;/a&gt;&lt;/li&gt; &lt;/ul&gt; &lt;/li&gt; &lt;li&gt;&lt;a href="#"&gt;菜单2&lt;/a&gt;&lt;/li&gt; &lt;!-- 其他菜单项 --&gt; &lt;/ul&gt; &lt;/nav&gt; ``` 接下来,我们用CSS来定义样式,使菜单看起来更加...

    可拖动换位照片墙

    &lt;div class="photo"&gt; &lt;img src="image1.jpg" data-index="1" draggable="true"&gt; &lt;/div&gt; &lt;div class="photo"&gt; &lt;img src="image2.jpg" data-index="2" draggable="true"&gt; &lt;/div&gt; &lt;!-- 更多照片... --&gt; &lt;/div&gt; `...

    青蛙换位问题Java实现

    青蛙换位问题是一个经典的计算机科学问题,通常出现在算法和数据结构的学习中。在这个问题中,我们假设有一排数字,目标是通过青蛙跳跃的方式将这些数字重新排列,使得每一步青蛙都只能从当前位置跳到相邻的位置,但...

    JAVA换位密码算法

    2. 使用`&lt;form&gt;`标签和`action`属性指定处理请求的Servlet。 3. 在Servlet中,获取请求参数(明文和密钥),调用上面的加密或解密方法。 4. 将处理结果设置为响应的一部分,返回到JSP页面显示。 **五、安全性与局限...

    组合数学全排列换位算法

    组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法组合数学全排列换位算法

    青蛙换位游戏算法实现C++ 回溯法

    青蛙换位游戏是一种经典的逻辑推理问题,通常出现在计算机科学中的算法设计与分析课程中,用于教授学生如何使用回溯法来解决复杂问题。在这个游戏中,有一排数字,我们需要通过一系列合法的操作将它们重新排列,使得...

    全排列的算法 翻转法 换位法 字典序法

    本篇将详细介绍三种解决全排列问题的算法:翻转法、换位法和字典序法。 1. **翻转法**: 翻转法是一种基于回溯思想的全排列算法。基本思路是从第一个元素开始,每次选择一个未使用的元素放置在当前排列的末尾,然后...

    青蛙换位问题

    总结来说,青蛙换位问题是一个利用回溯法求解的典型问题,涉及基本的搜索算法和状态空间的探索。通过理解和应用回溯法,我们可以找出所有可能的跳跃序列,同时也可以进行性能优化,提高问题求解的效率。实验报告和...

    CPSC452-CryptoCode

    ./cipher &lt;CIPHER&gt; &lt;KEY&gt; &lt;ENC&gt; &lt;INPUTFILE&gt; &lt;OUTPUT&gt; 密码名称: PLF-Playfair RTS-行换位 RFC-围栏 VIG-维格纳尔 CES-凯撒 密钥:要使用的加密密钥。 ENC / DEC:分别加密还是解密。 输入文件:从中读取输入...

    算法设计与分析 java(包含几种经典算法)

    试设计一个算法将子数组a[0:k]与a[k+1,n-1]换位。要求算法在最坏情况下耗时O(n),且只用到O(1)的辅助空间。 2.在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并...

    Java换位密码加密解密

    在Java中,我们通常使用字符数组来存储和操作这些字母。我们可以创建一个简单的类`ShiftCipher`,包含加密和解密的方法,其中加密方法将字符向前移动,解密方法则向后移动。 ```java public class ShiftCipher { ...

    黑马程序员 - Java基础教学 - 04 - 数组、进制转换、二维数组

    Java基础教学 - 数组、进制转换、二维数组 在Java基础教学中,数组是一个非常重要的概念。数组是多个相同类型的变量组成的集合,每个变量被称为一个元素,数组中的每个元素都有自己的下标或索引。下面将详细讲解...

    论文研究-等球Packing问题的序列对称换位算法.pdf

    为处理等球Packing问题, 在基本拟物算法的基础上设计了序列对称换位策略, 形成了一个启发式的序列对称换位算法。在球形容器内装填1~50个等球时, 此算法改进了其中45项当前记录。特别地, 此算法成功将68个半径为1的等...

    CSS3实现头像旋转效果

    &lt;title&gt;CSS3头像旋转效果&lt;/title&gt; &lt;style&gt; img{ border: #000 solid 2px; display: block; margin: 50px auto; border-radius: 50%; transition: all 2.0s; /* 过渡效果 */ } img:hover{ transform: ...

    动物换位游戏,动物换位游戏

    总的来说,动物换位游戏不仅锻炼了编程技巧,也对问题解决能力、算法设计和数据结构理解有很好的提升作用。通过这个项目,学生可以深入理解面向对象编程的核心思想,同时掌握基本的搜索算法和游戏设计原理。在实践中...

    动物换位游戏(代码+实验报告)

    总的来说,“动物换位游戏”是JAVA编程的一个有趣实践,它涵盖了面向对象编程、数据结构、算法和用户交互等多个重要概念,对于学习和提升JAVA编程技能有着显著的价值。同时,游戏设计的自由度也为开发者提供了创新和...

    python 换位密码算法的实例详解

    ### Python 换位密码算法的实例详解 #### 一、换位密码基本概念与原理 换位密码(Transposition Cipher)是一种简单的古典密码技术,它通过对明文中的字符顺序进行重新排列来达到加密的目的。在换位密码中,原始...

    Java实现动物换位游戏源码

    2. 数组和多维数组:游戏棋盘可以表示为二维数组,存储每个位置上的动物对象。 3. 排列和组合:游戏可能涉及对动物的排列进行操作,这需要理解和运用排列组合的数学知识。 4. 事件处理:使用Java AWT和Swing的事件...

    换位.CPP 加密算法

    oid jiami(); //加密函数 void jiemi(); //解密函数 //加密函数 void jiami() { ///输入明文字符串 int i=0,l,c,a;...printf("\n输入要加密的明文:");...l&lt;=(a+1)*6;l++) { in[l]=' '; } /////加密过程

Global site tag (gtag.js) - Google Analytics