对数组进行循环移位算法
这个是在微软编程里看到的一个算法题，拿来等高手解答
将一个含有n个元素的数组向右循环移动k位，要求时间复杂度是O(n)，且只能使用两个额外的变量
某月某日某某人
12 years, 9 months ago
Answers
k % = n;
//求出n和k的最大公约数（欧几里得辗转相除法）
int g1,g2;
g1 = n;
g2 = k;
while(g2 != 0)
{
g1 = g1 % g2;
g1 = g1 ^ g2;
g2 = g1 ^ g2;
g1 = g1 ^ g2;
}
//复用变量g1,g2做为循环变量
for(g1--;g1>=0;g1--)
{
for(g2 = g1; (g2 + n - k) % n != g1; g2 = (g2 + n - k) % n)
{
a[g2] = a[g2] ^ a[(g2 + n - k) % n];
a[(g2 + n - k) % n] = a[g2] ^ a[(g2 + n - k) % n];
a[g2] = a[g2] ^ a[(g2 + n - k) % n];
}
}
原理：循环移位时，每个元素m移到(m+k) % n的位置上，而(m+k)%n移到(m+2k)%n的位置上……
当n与k互质时，可以证明m, m+k, m+2k, ..., m + (n-1)k模n的结果互不相等，刚好构成一个循环；否则，会构成(n,k)（n与k的最大公约数）个循环。分别处理这(n,k)个循环就可以得到结果。
killed
answered 12 years, 9 months ago