数组循环移位问题

发表于 2019-03-11 更新于 2022-09-13 阅读次数：
今天面试遇到的一道题。与参考资料的第一篇文章类似。
另外可以参考STL源码中 rotate() 函数的实现思路。
//TODO 有待填坑
测试几种算法的运行效率

public class Solution {

    //rotate_right
    public static void tripleReverse(int[] nums, int K) {
        int length = nums.length;
        reverse(nums, 0, length - K - 1);
        reverse(nums, length - K, length - 1);
        reverse(nums, 0, length - 1);
    }

    private static void reverse(int[] nums, int start, int end) {
        int sum = start + end;
        int temp;
        for (int i = start; i <= (start + end) / 2; ++i) {
            temp = nums[i];
            nums[i] = nums[sum - i];
            nums[sum - i] = temp;
        }
    }

    //rotate_right
    public static void doubleSwap(int[] nums, int K) {
        int start = 0;
        int end = nums.length;
        int middle = nums.length - K;
        int i = middle;
        int temp;

        while (true) {
            temp = nums[start];
            nums[start] = nums[i];
            nums[i] = temp;
            ++start;
            if (++i == end) {
                if (start == middle) {
                    break;
                }
                i = middle;
            } else if (start == middle) {
                middle = i;
            }
        }
    }

    // rotate left
    // if want to rotate right, add [K = nums.length - K] at the beginning
    public static void rotate_GCD(int nums[], int K) {
        int length = nums.length;
        int front, post, temp;
        for (int i = 0; i < GCD(length, K); ++i) {
            temp = nums[i];
            front = i;
            while (true) {
                post = front + K;
                if (post >= length) {
                    post = post - length;
                }
                if (post == i) {
                    break;
                }
                nums[front] = nums[post];
                front = post;
            }
            nums[front] = temp;
        }
    }

    private static int GCD(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return GCD(b, a % b);
        }
    }

    public static void main(String[] args) {
        // 一亿个整数，大概需要三百多兆的内存
        int[] array = new int[1_0000_0000];
        for (int i = 0; i < 1_0000_0000; ++i) {
            array[i] = i;
        }

        long startTime;
        long durationNanoSecond;
        double durationMicroSecond;

        startTime = System.nanoTime();
        tripleReverse(array, 1000000);
        durationNanoSecond = System.nanoTime() - startTime;
        durationMicroSecond = durationNanoSecond / 1_000;
        System.out.println(String.format("[tripleReverse]Time:%f 微秒",
        durationMicroSecond));

        startTime = System.nanoTime();
        doubleSwap(array, 1000000);
        durationNanoSecond = System.nanoTime() - startTime;
        durationMicroSecond = durationNanoSecond / 1_000;
        System.out.println(String.format("[doubleSwap]Time:%f 微秒", durationMicroSecond));

        startTime = System.nanoTime();
        rotate_GCD(array, 1000000);
        durationNanoSecond = System.nanoTime() - startTime;
        durationMicroSecond = durationNanoSecond / 1_000;
        System.out.println(String.format("[rotate_GCD]Time:%f 微秒", durationMicroSecond));

        System.out.print("[result]");
        for (int i = 0; i < 10; i++) {
            System.out.printf("%d,", array[i]);
        }
    }
}