189. 旋转数组（Rotate Array）

将包含* n* 个元素的数组向右旋转 *k *步。

例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。
注意:
尽可能找到更多的解决方案，这里最少有三种不同的方法解决这个问题。
[显示提示]
提示:
要求空间复杂度为 O(1)

关联的问题: 反转字符串中的单词 II

解法一，O(n) 的空间复杂度

思路：创建另外一个数组记录元素旋转后的位置
finalLocation = (currentLocation + k ) % n

class Solution {
    public void rotate(int[] nums, int k) {
       
         if (nums.length < 2 || k < 1 || k % nums.length == 0) {
            return;
        }
        
        // O(n) 的空间复杂度
        int[] result = new int[nums.length];

        // 用另外一个数组记录元素旋转后的位置
        for (int i = 0; i < nums.length; i++) {
            int fIndex = (i + k) % nums.length;
            result[fIndex] = nums[i];
        }
        
        // 赋值给原数组
        for (int i = 0; i < nums.length; i++) {
            nums[i] = result[i];
        }
     
    }
}

解法二，空间复杂度为 O(1)

如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。

思路：把原数组划分为两个部分来看：前 n - k 个元素 [1,2,3,4]和 后k个元素 [5,6,7]，进行分开处理

1. 定义 reverse 逆转方法：将数组元素反转，比如 [1,2,3,4] 逆转后变成 [4,3,2,1]
2. 对前 n - k 个元素 [1,2,3,4] 进行逆转后得到 [4,3,2,1]
3. 对后k个元素 [5,6,7] 进行逆转后得到 [7,6,5]
4. 将前后元素 [4,3,2,1,7,6,5] 逆转得到：[5,6,7,1,2,3,4]
   注意：还要处理 k > 数组长度的情况，对 k 进行取模

class Solution {
    public void rotate(int[] nums, int k) {
        // 旋转即是元素顺序轮转的意思
        
        if (nums.length < 2 || k < 1 || k % nums.length == 0) {
            return;
        }
        
        // 处理 k 大于 数组长度的情况
        if (k > nums.length) {
            k = k % nums.length;
        }

        // 对前 n - k 个元素 [1,2,3,4] 进行逆转后得到 [4,3,2,1] 
        reverse(nums, 0, nums.length - 1 - k);
        // 对后k个元素 [5,6,7] 进行逆转后得到 [7,6,5]
        reverse(nums, nums.length - k, nums.length -1);
        // 将前后元素 [4,3,2,1,7,6,5] 逆转得到：[5,6,7,1,2,3,4]
        reverse(nums, 0, nums.length - 1);
        
    }
    
    // 逆转数组指定区间内的元素，比如 [1,2,3,4] 逆转后变成  [4,3,2,1] 
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }
}

解法三，每次操作一位元素进行旋转操作，O(n) 的时间复杂度

思路：依旧利用 (i + k) % n 等于新 index 的思路，不过这是每次调换一个元素，后一个元素的调换基于上一个的位置。

比如：数组 [1,2,3,4,5,6,7]，n = 7, k = 3
1.记录数组第一个元素 currentNum 和 currentIndex 信息
2.计算第一位元素进行旋转后的 newIndex
3.使用 temp 记录数组 newIndex 位置的元素值
4.调换第一位元素值到数组 newIndex 位置上，此时数组 [1,2,3,1,5,6,7]
5.此时 currentIndex 和 newIndex 不相等，记录当前要调换的值 currentNum = temp，进行下一次调换，
6.此时要调换的元素值就是 currentNum，其原来的位置就是 newIndex，然后计算该元素旋转后的新 newIndex 值
以此类推，如果判断 currentIndex = newIndex 说明两个位置的元素相互交换完成，那直接往后推一位

class Solution {
    public void rotate(int[] nums, int k) {
        // 旋转即是元素顺序轮转的意思
        
        if (nums.length < 2 || k < 1 || k % nums.length == 0) {
            return;
        }
        
        int currentNum = nums[0];
        int currentIndex = 0;
        int newIndex = 0;
        int i = 0;
        
        while (i++ < nums.length) {
            newIndex = (newIndex + k) % nums.length;
            int temp = nums[newIndex];
            nums[newIndex] = currentNum;
            
            if (currentIndex == newIndex) {
                currentNum = nums[++newIndex];
                ++currentIndex;
            } else {
                currentNum = temp;
            }
        }
        
    }
    
    // 逆转数组指定区间内的元素，比如 [1,2,3,4] 逆转后变成  [4,3,2,1] 
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }

}