【Leetcode】189. Rotate Array

Descirption

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

[show hint]

Related problem: Reverse Words in a String II

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Solution

public void rotate(int[] nums, int k) {
        if (k <= 0 || nums.length == 0) {
            return;
        }
        int len = nums.length;
        int realDis = k % len;
        int[] newArray = new int[len];
        for (int i = 0; i < realDis; i++) {
            newArray[i] = nums[i + len - realDis];
        }
        for (int j = realDis; j < len; j++) {
            newArray[j] = nums[j - realDis];
        }
        for (int m = 0; m < len; m++) {
            nums[m] = newArray[m];
        }
        return;
    }

Result

AC

Analyse

这种方法很简单，就是简单的替换，O(n)的时间复杂度，O(n)的空间复杂度。

Optimization

First

public void rotate(int[] nums, int k) {
        if (k <= 0 || nums.length == 0) {
            return;
        }
        int realDis = k % nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, realDis - 1);
        reverse(nums, realDis, nums.length - 1);
        return;
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            nums[start] ^= nums[end];
            nums[end] ^= nums[start];
            nums[start] ^= nums[end];
            start++;
            end--;
        }
        return;
    }

Second

public void rotate(int[] nums, int k) {
        int step = k % nums.length;
        int gcd = findGcd(nums.length, step);
        int position, count;
        for (int i = 0; i < gcd; i++) {
            position = i;
            count = nums.length / gcd - 1;
            for (int j = 0; j < count; j++) {
                position = (position + step) % nums.length;
                nums[i] ^= nums[position];
                nums[position] ^= nums[i];
                nums[i] ^= nums[position];
            }
        }
        return;
    }

    public int findGcd(int a, int b) {
        return (a == 0 || b == 0) ? (a + b) : findGcd(b, a%b);
    }

Analyse

这个方法的思路很简单，第一个优化的措施是三步替换，替换的过程一步就可以看出，需要熟悉这个方法，时间复杂度是O(n)，空间复杂度是O(1)。第二个优化的思路值得学习，首先需要明确一个点就是：我们如果直接替换的话是需要怎样的步骤进行操作。这个时候就要提出来gcd，首先求出两者的最大公约数，这个最大公约数意味着该数字要替换多少轮，如果是第一轮就从0开始，然后依次递推，第二轮从1开始，第三轮从2开始等。然后在每一轮下，替换的次数就是数组长度除以gcd减去1得到要比较的轮数，每一轮都是开始的那个数，依次往后数step个数字，按照数组长度循环走，直到能走到和开始出发的数字重合。但是重合的时候就已经是被计算出来了，那么这样计算的结果是这个j只是计算了次数，看第n轮的开始的数字能替换多少次。