leetcode 热题 100_轮转数组

题解一：

        新数组存储：另外用一个数组存储移动后的结果，再复制回原数组。

class Solution {
    public void rotate(int[] nums, int k) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result[(i + k) % nums.length] = nums[i];
        }
        System.arraycopy(result, 0, nums, 0, nums.length);
    }
}

题解二：

        原数组移动：在原数组上直接将nums[i]移动到nums[i+k]，需要临时存储被覆盖的值nums[i+k]，被覆盖的值则继续向后移动覆盖nums[i+2k]，循环直到回到第一个开始移动的值。，这个过程可能有若干元素没有被移动，因此需要从nums[i+1]开始重复这个过程。如何判断所有的值都被移动过一次呢，另外用一个count计数，每次移动都+1，直到等于数组长度。这个解法效率较低并且较难理解，不推荐。

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = 0;

        for (int i = 0; count < n; i++) {
            for (int pre = nums[i], next, index = i; ; ) {
                next = (i + k) % n;

                int temp = nums[next];
                nums[next] = pre;
                pre = temp;

                count++;

                i = (i + k) % n;
                if (i == index) break;
            }
        }
    }

}

题解三：

        数组翻转：将整个数组进行反转，再以下标[0,k-1]，[k,nums.length-1]左右两段分别进行翻转就得到最终结果，很巧妙的解法。

class Solution {
    public void reserve(int[] a, int begin, int end) {
        for (; begin < end; begin++, end--) {
            int temp = a[begin];
            a[begin] = a[end];
            a[end] = temp;
        }
    }

    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        reserve(nums, 0, nums.length-1);
        reserve(nums, 0, k - 1);
        reserve(nums, k, nums.length-1);
    }
}