`

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

阅读更多

子数组换位问题

 

      设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
根据公式可以推出更复杂的

相关推荐

    计算机算法设计与分析实验报告.doc

    分治法是计算机科学中一种非常重要的算法设计范式,它通过将问题分解为若干个较小的子问题,递归解决这些子问题,然后再将子问题的解合并,以得到原问题的解。这种策略在许多经典算法中得以应用,如快速排序、二分...

    《C 程序员面试算法宝典》读书笔记模板x.pptx

    书中将程序员面试笔试过程中典型算法类真题尽收囊中,在题目的广度上,通过各种渠道,搜集了近 3 年来几乎所有 IT 企业面试笔试算法高频题目,所选择题目均为企业招聘使用的真题。在题目的深度上,本书由浅入深,...

    C/C++常用算法手册.秦姣华(有详细书签).rar

    》主要定位于有一定C/C++语言编程基础、想通过学习算法与数据结构提升编程水平的读者,也可作为具有一定编程经验的程序员以及大中专院校学生学习数据结构和算法的参考书。 第1篇 算法基础篇 1 第1章 算法概述 2 ...

    数据结构及算法C语言实现代码集[推荐下载]

    问题算法 顺序栈.c 顺序表.c 顺序队列.c ./其它&#58; c语言窗体实例.zip 傻瓜递归.c 冒泡法改进.c 小字库DIY-.c 小字库DIY.c 小白鼠钻迷宫.c 扫描码.C 挽救软盘.c 汉字字模.c 神经元模型.c 穷举搜索法.c 简单数据库...

    经典数据结构算法c语言实现代码(大全)

    N皇后问题回溯算法.txt ping.txt re.txt source.txt winsock2.txt ww.txt 万年历.txt 万年历的算法 .txt 乘方函数桃子猴.txt 乘法矩阵.txt 二分查找1.txt 二分查找2.txt 二叉排序树.txt 二叉树.txt ...

    史上最全经典数据结构算法c语言实现代码合集

    N皇后问题回溯算法.txt ping.txt re.txt source.txt winsock2.txt ww.txt 万年历.txt 万年历的算法 .txt 乘方函数桃子猴.txt 乘法矩阵.txt 二分查找1.txt 二分查找2.txt 二叉排序树.txt 二叉树.txt ...

    C语言经典算法

    根据给定文件的信息,我们可以将其中涉及的知识点分为以下几个部分:C语言基础知识、经典算法案例、数据结构实现、数学问题解决方法以及特定编程技巧。接下来,我们将对这些知识点进行详细的阐述。 ### C语言基础...

    数据结构(C语言)代码实例19

    "换位递归.txt"可能是一个使用递归实现的数组元素交换的算法。递归是编程中的强大工具,尤其在处理树结构或分治策略的问题时,它可以使代码简洁且易于理解。 最后,"自己调用自己.cpp"是一个自我引用的程序,通常指...

Global site tag (gtag.js) - Google Analytics