O(n)时间O(1)辅助空间，循环移位
这一道，google的笔试题，网易也用过，学校的数据结构题目系统也有，之前我都是卡着机器出的
现在整理一下
一 3次翻转做法
/*about 循环移位
实例：abcdefgh 向左循环移位3位
结果 defghabc
1.abc做翻转
cba defgh
2 defgh做翻转 cba
hgfed
3.第二结果全部在做翻转 成为
defghabc */
template<class T>
void reverse(T a[],int i,int j)
{
while(i < j)
{
swap(a[i],a[j]);
++i;
--j;
}
}
template<class T>
void exch1(T a[],int n,int k)
{
reverse(a,0,k-1);
reverse(a,k,n-1);
reverse(a,0,n-1);
} reverse(a,0,k-1); // k/2
reverse(a,k,n-1); // (n-k)/2
reverse(a,0,n-1); // n/2
为 k/2+(n-k)/2+k/2=n/2 + n/2 = n
二 ...
posted on 2009-11-26 12:40
爬 阅读(1255)
评论(3) 编辑 收藏 引用 所属分类:
algorithm