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
爬 閱讀(1266)
評論(3) 編輯 收藏 引用 所屬分類:
algorithm