/**//*
问题描述:
设a[0:n-1]是一个有n个元素的数组，k(0<=k<=n-1)是一个非负整数．试设计一个算法将子数组
a[0:k]与a[k+1:n-1]换位．要求算法在最坏情况下耗时O(n), 且只用到O(1)的辅助空间．
*/
/**//*求解思想：
算法的时间复杂度很容易保证，想弄出O(n*n)的算法都会很困难，关键是要保证只用到O(1)的辅助空间。
可以用递归分治的算法思想。
*/
public class ChangePosition
{
public void swap(int a[],int begin,int second,int size)
{
int tmp=0;
for(int i=0;i<size;i++)
{
tmp=a[i+begin];
a[i+begin]=a[i+second];
a[i+second]=tmp;
}
}
public void change(int a[],int begin,int k,int nlen)
{
int first=k+1;
int second=nlen-first;
if(second<=0||first<0)
{
return ;
}
else
{
if(first<=second)
{
swap(a,begin,first+begin,first);
change(a,begin+first,first-1,nlen-first);
}
else
{
swap(a,begin,begin+first,second);
change(a,begin+second,first-1-second,nlen-second);
}
}
}
public void print(int[]a,int size)
{
for(int i=0;i<size;i++)
{
System.out.print(a[i]+" ");
}
System.out.println();
}
/**//*
第二种方法的思想是我们把一个数组的两个部分分别逆序，然后将整个数组再次逆序，
逆序两次以后就可以得到该问题的解，如果可以想到的话问题就很简单了!
*/
public void reverse(int[]a,int begin,int end)
{
int n=(begin+end)/2;
int tmp=0;
for(int i=begin;i<=n;i++)
{
tmp=a[i];
a[i]=a[end];
a[end]=tmp;
end--;
}
}
public static void main(String[] args)
{
int[] a={0,1,2,3,4,5,6,7,8,9};
ChangePosition cp=new ChangePosition();
cp.change(a,0,1,10);
cp.print(a,10);
int[] b={0,1,2,3,4,5,6,7,8,9};
cp.reverse(b,0,2);
cp.reverse(b,3,9);
cp.reverse(b,0,9);
cp.print(b,10);
}
}posted on 2008-06-09 21:04
夏日清风 阅读(594)
评论(0) 编辑 收藏 所属分类:
算法