算法设计题1VIP专享VIP免费

出2个算法设计题，每个20分。1.设a[0:n-1]是有n个元素的数组，k(0≤k≤n-1)是一个非负整数。试设计一个算法将子数组a[0:k-1]和a[k: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[low1]<->a[low2]a[low1+1]<->a[low2+1]...a[high1]<->a[high2]voidsa[],intlow1,inthigh1,intlow2,inthigh2){inttemp;while(low1<=high1){temp=a[low1];a[low1]=a[low2];a[low2]=temp;low1++;low2++;}}//利用分治算法，每次选择最小的数组进行换位voidpatition(inta[],intlow,intk,inthigh){if(low//交换数组的两段大小相等的范围的对应数据//a[low1]<->a[low2]a[low1+1]<->a[low2+1]...a[high1]<->a[high2]voidsa[],intlow1,inthigh1,intlow2,inthigh2){inttemp;while(low1<=high1){temp=a[low1];a[low1]=a[low2];a[low2]=temp;low1++;low2++;}}//利用分治算法，每次选择最小的数组进行换位voidpatition(inta[],intlow,intk,inthigh){if(lowusingnamespacestd;#defineMAXNUM100//下面函数将数组段a[s:t]中元素循环右移位k个位置voidshiftright(inta[],ints,intt,intk){inti=0;intj=0;for(i=0;is;j--){a[j]=a[j-1];}a[s]=tmp;}}//下面函数用于在数组段中a[left:right]中搜索元素x的插入位置intbinarySearch(inta[],intx,intleft,intright){intmid;while(left<=right){mid=left+(right-left)/2;if(x==a[mid]){returnmid;}if(x>a[mid]){left=mid+1;}else{right=mid-1;}}if(x>a[mid]){returnmid;}else{returnmid-1;}}//向右循环移位合并算法//length:数组的长度voidmergef...