指定一个数组,比如整数或字符串, 长度为N, 将其循环右移K位.
以下是我的解法: 只需要遍历一次数组即可. 空间复杂度是o(1), 时间复杂度是o(N).
不同于其他的解法: 1) 不需要求GCD(N,K) 2)不需要遍历2遍数组(STL源码中的reverse算法)
void Output(int *pBuffer, int nCount)
{
if(!pBuffer || !nCount) return;
for (size_t i = 0; i < nCount; i++)
{
printf(" %d ", pBuffer[i]);
}
printf("\n");
}
void ShiftN(int *pBuffer, int nCount, int nShiftN)
{
if(!pBuffer || !nCount || !nShiftN) return;
nShiftN %= nCount;
int nIndex = 0;
int nStart = nIndex;
int nTemp = pBuffer[nIndex];
for (size_t i = 0; i < nCount; i++)
{
nIndex = (nIndex + nShiftN) % nCount;
pBuffer[nIndex] ^= nTemp ^=
pBuffer[nIndex] ^= nTemp ;
if(nIndex == nStart)
{
nStart ++;
nIndex = nStart;
nTemp = pBuffer[nIndex];
}
}
}
int main(int argc, char* argv[])
{
int buffer[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int nCount = sizeof(buffer) / sizeof(int);
Output(buffer, nCount);
ShiftN(buffer, nCount, 8);
Output(buffer, nCount);
return 0;
}
posted on 2008-12-30 19:50
vcfly 阅读(3537)
评论(2) 编辑 收藏 引用 所属分类:
algorithm 、
c/c++