数组k平移三种方法（java）

上代码，本文用了三种方法实现，时间复杂度不一样，空间复杂度都是o(1)：

public class ArrayKMove {

    /**
     * 问题：数组的向左k平移，k小于数组长度
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        ArrayKMove kmove = new ArrayKMove();
        kmove.methodOne();
        kmove.methodTwo();
        kmove.methodThree();
    }

    private static final int i = 10000;
    private static final int testNum = 1000;
    private int a[];
    private long startTime = 0, timeSpan = 0;

    public ArrayKMove() {
        a = new int[i];
        for (int j = 0; j < i; j++) {
            a[j] = j;
        }
    }

    public void printArray() {
        for (int j = 0; j < i; j++) {
            System.out.println(a[j]);
        }
    }

    public void methodOne() {
        this.startTime = System.currentTimeMillis();
        for (int k = 1; k <= testNum; k++) {
            for (int j = 0; j < k; j++) {
                this.moveArrayFirstToLast();
            }
        }
        this.timeSpan = System.currentTimeMillis() - this.startTime;
        System.out.println("第一种方法消耗时间：" + timeSpan + "毫秒");
    }

    public void moveArrayFirstToLast() {
        int m = a[0];
        for (int j = 1; j < i; j++) {
            a[j - 1] = a[j];
        }
        a[i - 1] = m;
    }

    public void methodTwo() {
        this.startTime = System.currentTimeMillis();
        for (int j = 1; j <= testNum; j++) {
            this.swapArray(1, j);
            this.swapArray(j + 1, i);
            this.swapArray(1, i);
        }
        this.timeSpan = System.currentTimeMillis() - this.startTime;
        System.out.println("第二种方法消耗时间：" + timeSpan + "毫秒");
    }

    public void swapArray(int start, int end) {
        for (int s = start - 1, e = end - 1; s < e; s++, e--) {
            int temp = a[s];
            a[s] = a[e];
            a[e] = temp;
        }
    }

    public int gcdTwoInt(int m, int n) {
        if (m <= 0 && n <= 0)
            return 0;
        if (m <= 0 || n <= 0)
            return m <= 0 ? n : m;
        int g;
        while (n > 0) {
            g = m % n;
            m = n;
            n = g;
        }
        return m;
    }

    public void moveByGCD(int k) {
        if (k <= 0)
            return;
        int m = this.gcdTwoInt(k, i);
        for (int j = 0; j < m; j++) {
            int c = a[j];
            int p;
            for (p = (j + k) % i; p != j; p = (p + k) % i) {
                a[(p - k + i) % i] = a[p];
            }
            a[(p - k + i) % i] = c;
        }
    }

    public void methodThree() {
        this.startTime = System.currentTimeMillis();
        for (int j = 1; j <= testNum; j++) {
            this.moveByGCD(j);
        }
        this.timeSpan = System.currentTimeMillis() - this.startTime;
        System.out.println("第三种方法消耗时间：" + this.timeSpan + "毫秒");
    }
}

方法一：基本方法，每次左移一位，移动k次即可，但是时间复杂度是o(kn)，这个方法可以用牺牲空间复杂度来提升时间效率，即用一个数组保存要平移的k个数据，把原数组直接平移k位后，再把k位数据直接插在后面k个位置即可，时间复杂度o(n)

方法二：先把前k位翻转，再把后面的n-k位翻转，然后整体翻转，这个画图可以证明。

方法三：不是很好理解，基本思路就是，循环替换，用i+k的值替换i处的值，但是是循环，也就是不能数组越界，还有就是要分m条路线，m是n和k的最大公约数。

测试规模:

数组大小10000，

测试次数1000，

每次平移的位数依次为1-1000次；

 

测试结果：

第一种方法消耗时间：5364毫秒

第二种方法消耗时间：21毫秒

第三种方法消耗时间：129毫秒

 

结果分析：

三种方法空间复杂度都是o(1)

时间复杂度依次为o(kn)、o(3n)、o(n)

但是测试时间第三种方法消耗的时间却比第二种大，原因是第三种方法中有求解两个最大公约数的操作，而且有运算较为复杂的求余运算，所以消耗时间增加，方法二中只有交换赋值的操作，比较简单。