数组元素循环右移

将一个int[]型数组右移k位，要求最小的空间占用。

一个数组A中存有N(N>0)个数, 在不允许使用任何另外数组的前提下, 将每个整数循环右移M(M>0)位, 考虑移动数据的次数尽量少, 要如何设计移动方法?

示意图

分析1

当然, 最简单的方法莫过于直接每次向右移动一个, 要移动M位, 就移动M次. 代码如下：

//传入操作数组和移动的位数

void moveRight(int Arr[], int M)

{

    //保存下数组的最后一个数

    int endNum = Arr[N-1];

    //将0~N-2位数向后移动一位

    int i;

    for(i=N-1; i>0; i--){

        Arr[i] = Arr[i-1];

    }

    //将最后一位数放在第一位

    Arr[0] = endNum;

}

时间复杂度:

每移动一位就需要做N次赋值操作, 如果移动M位,则需要做NM次赋值操作

分析2

我们先将数组分成两部分, 设后面M位为数组b, 前面N-M位为数组a, 那么怎么数组的组成就是ab.

原始数组是ab, 我的目的是将这个数组变成ba

第一步:将整个长度为N的数组倒置得到 b-1a-1 .

第二步:将 b-1 数组和 a-1 数组分别倒置, 得到 ba数组.

//该函数实现将两个变量互换

void Swap(int *a, int *b)

{

    //得到中间变量

    *a = *a ^ *b;

    //b变量获取到a的值

    *b = *b ^ *a;

    //a变量通过中间变量获取到当时b的值

    *a = *a ^ *b;

}

void moveRight(int Arr[], int N, int M)

{

    int i, j;

    //转置所有的元素

    for(i=N-1, j=0; j