O(n)時間O(1)輔助空間，循環(huán)移位
這一道，google的筆試題，網(wǎng)易也用過，學(xué)校的數(shù)據(jù)結(jié)構(gòu)題目系統(tǒng)也有，之前我都是卡著機器出的
現(xiàn)在整理一下
一 3次翻轉(zhuǎn)做法
/*about 循環(huán)移位
實例：abcdefgh 向左循環(huán)移位3位
結(jié)果 defghabc
1.abc做翻轉(zhuǎn)
cba defgh
2 defgh做翻轉(zhuǎn) cba
hgfed
3.第二結(jié)果全部在做翻轉(zhuǎn) 成為
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
爬 閱讀(1291)
評論(3) 編輯 收藏 引用 所屬分類:
algorithm