题目

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

说明:

• 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
• 要求使用空间复杂度为 O(1) 的 原地 算法。

思路

借助额外空间

这个思路很简单，定位到需要旋转的位置，重新构造数组即可，但不符合题意，题目要求我们原地实现。

旋转元素

1. 将整个数组反转
2. 将数组[0, k - 1]区间内反转
3. 将[k, len-1]区间内反转

完成。

实现

借助额外空间

class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        if (k % len == 0) return ;
        k = k % len;
        int[] temp = new int[len];
        int count = 0;
        for (int i = len - k; i < len; i++) {
            temp[count++] = nums[i];
        }
        for (int i = 0; i < len - k; i++) {
            temp[count++] = nums[i];
        }
        for (int i = 0; i < len; i++) {
            nums[i] = temp[i];
        }
    }
}

旋转元素

class Solution {
    public void reverse(int[] nums, int l, int r) {
        while (l < r) {
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            l++;
            r--;
        }
    }

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