# 189. Rotate Array
###### tags: `Leetcode` `Medium` `Array`
Link: https://leetcode.com/problems/rotate-array/
## 思路
### 思路一 暴力解法
新开一个array，存要换到前面的数字，然后把要换到后面的数字移到后面，再把存到新array里面的数字放到前面
### 思路二 翻转Array (Very Tricky)
比较翻转过的array和答案，就会发现答案=翻转过的array，再把前k个数和后面的数各自翻转过的结果
### 思路三 (很绕 多写几遍)
我们从位置 00 开始，最初令 temp=nums[0]。根据规则，位置 00 的元素会放至 (0+k)mod n 的位置，令 x=(0+k)mod n，此时交换 temp 和 nums[x]，完成位置 x 的更新。然后，我们考察位置 x，并交换 temp 和 nums[(x+k)mod n]，从而完成下一个位置的更新。不断进行上述过程，直至回到初始位置 0。

容易发现，当回到初始位置 0 时，有些数字可能还没有遍历到，此时我们应该从下一个数字开始重复的过程，可是这个时候怎么才算遍历结束呢？我们不妨先考虑这样一个问题：从 0 开始不断遍历，最终回到起点 0 的过程中，我们遍历了多少个元素？

count的由来：因为从 0 开始不断遍历，最终又回到起点 0，这个过程走了a圈（a正为整数），每圈的长度为n。 这个过程中，走的每一步的长度为k,共走过了b个元素，所以走的总步长为bk，也即这a圈的长度，即a*n=b*k。 即 a*n 一定为 n,k 的公倍数。又因为我们在第一次回到起点时就要结束，因此a要最小，故a*n就是n,k的最小公倍数lcm(n,k) ， 因此 b 就为lcm(n,k)/k，这说明从起点再次回到起点的过程中会访问到 lcm(n,k)/k 个元素。 为了访问到所有的元素，我们需要进行遍历的次数为，n/lcm(n,k)/k = n*k/lcm(n,k) = gcd(n,k)(最大公约数和最小公倍数的关系) 即需要遍历的次数为n和k的最大公约数。

或者也可以用单独的变量count跟踪当前已经访问的元素数量，当count = n时，结束遍历过程。

## Code
### 思路一

class Solution {
    public void rotate(int[] nums, int k) {
        k = k%nums.length;
        int[] new_nums = new int[k];
        int pos = 0;
        for(int i = nums.length-k;i < nums.length;i++){
            new_nums[pos] = nums[i];
            pos++;
        }
        for(int i = nums.length-k-1;i >= 0;i--){
            nums[i+k] = nums[i];
        }
        for(int i = 0;i < k;i++){
            nums[i] = new_nums[i];
        }
        
        return;
    }
}

### 思路二

class Solution {
    public void rotate(int[] nums, int k) {
        k = k%nums.length;
        reverseArray(0,nums.length-1,nums);
        reverseArray(0,k-1, nums);
        reverseArray(k, nums.length-1, nums);
        return;
    }
    public static void reverseArray(int start, int end, int[] nums){
        int temp;
        while(start<end){
            temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

### 思路三

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }
    }

    public int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }
}

没有计算遍历次数，只是数遍历了几个元素，遍历元素个数=nums.length时，就break的版本

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = 0;
        for(int i = 0;i < n;i++){
            int current = i;
            int prev = nums[i];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while(current != i);
            if(count == n){
                break;
            }
        }
        return;
    }
}

## Result
### 思路一
Your runtime beats **35.30 %** of java submissions.
Your memory usage beats **15.36 %** of java submissions.
### 思路二
Your runtime beats **100.00 %** of java submissions.
Your memory usage beats **90.49 %** of java submissions.
### 思路三
Your runtime beats **35.30 %** of java submissions.
Your memory usage beats **49.92 %** of java submissions.
## 注意
注意do while的使用~