随笔-6  评论-4  文章-0  trackbacks-0

指定一个数组,比如整数或字符串, 长度为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)  编辑 收藏 引用 所属分类: algorithmc/c++

评论:
# re: 数组 循环位移 或 循环移动 (左移 或 右移) K位(转移自博客园) 2009-05-26 19:50 | ruory
C语言真的挺难学,我肯定会挂科!
  回复  更多评论
  
# re: 数组 循环位移 或 循环移动 (左移 或 右移) K位(转移自博客园) 2009-10-16 00:14 | 减肥中的小朋友
学这个会死人的,超难啊~~~  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理