將包含* n* 個元素的數(shù)組向右旋轉(zhuǎn) *k *步。

例如，如果 n = 7 , k = 3，給定數(shù)組 [1,2,3,4,5,6,7] ，向右旋轉(zhuǎn)后的結(jié)果為 [5,6,7,1,2,3,4]。

注意:

盡可能找到更多的解決方案，這里最少有三種不同的方法解決這個問題。

提示:

要求空間復雜度為 O(1)

分析：

題意明顯，就是數(shù)組內(nèi)換位置。這里可能會有一個誤區(qū)，空間復雜度要求為O(1)，并不是說不能創(chuàng)建數(shù)組，可以創(chuàng)建，但不能讓創(chuàng)建的數(shù)組超過常數(shù)級別的空間復雜度。另外K可以通過取模運算，避免重復的換位操作。各位小伙伴，八仙過海，各顯神通，拿下這道題吧！

接下來給出 4 種Java的解法，推薦度由低到高。

解法一：

優(yōu)點：不用創(chuàng)建新數(shù)組。
缺點：太耗時，平臺可能因為耗時太長而不通過。

思路：向右旋轉(zhuǎn)K步可以分解為做K次K=1的旋轉(zhuǎn)，那么可以讓每個元素都向右移1位，最后1位移到開頭位置，總共做k次這種全局移位即可。

Java代碼如下：

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

        k = k % nums.length;

        int currentCache = 0;
        int targetCache = 0;
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (j == nums.length - 1) {
                    nums[0] = currentCache;
                    break;
                }

                if (j == 0) {
                    currentCache = nums[j];
                }
                targetCache = nums[j + 1];
                nums[j + 1] = currentCache;

                currentCache = targetCache;
            }
        }
    }

解法二：

優(yōu)點：速度比解法一快很多。
缺點：需要新創(chuàng)建數(shù)組。

思路：這是最容易想到的方法，創(chuàng)建一個新數(shù)組，內(nèi)容和原數(shù)組保持一致，然后將新數(shù)組的每一個元素按照腳標加k的新腳標放入原數(shù)組對應的位置。這樣原數(shù)組就完成了新賦值。

Java解答如下：

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


        int[] newNums = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            newNums[i] = nums[i];
        }

        int index;
        for (int i = 0; i < nums.length; i++) {
            index = (i + k) % nums.length;
            nums[index] = newNums[i];
        }
    }

解法三：

優(yōu)點：速度非常快。
缺點：需要創(chuàng)建一個比原數(shù)組長的新數(shù)組。

思路：由于是向右旋轉(zhuǎn)k位，原數(shù)組的 [0, length - k) 個元素將向后移動k位，最終移到數(shù)組[k, length)的位置；而原數(shù)組的 [length - k, length) 個元素將會移動到數(shù)組的前面，占據(jù)了[0, k)的位置。
由此，創(chuàng)建一個新的長度是 length + k 的新數(shù)組，讓新數(shù)組 [k, length + k) 的位置存放原數(shù)組的 [0, length)；然后讓新數(shù)組的 [0, k) 位存放原數(shù)組的 [length - k, length) 位。此時新數(shù)組的 [0, length) 就是原數(shù)組旋轉(zhuǎn)之后的結(jié)果，再依次拷貝回原數(shù)組即可。

Java解答如下：

    public void rotate(int[] nums, int k) {
        int length = nums.length;
        if (length == 0 || length == 1) {
            return;
        }
        k %= length;
        int[] newnums = new int[length + k];
        System.arraycopy(nums, 0, newnums, k, length);
        System.arraycopy(nums, length - k, newnums, 0, k);
        System.arraycopy(newnums, 0, nums, 0, length);
    }

解法四：

優(yōu)點：不用創(chuàng)建新數(shù)組，速度很快。
缺點：僅僅比解法三慢幾毫秒。

思路：這里利用了一個小技巧。把原數(shù)組腳標為 0和length - 1的兩個元素交換位置，再把 1和length - 2兩個元素交換，依次類推直到整個數(shù)組順序正好反轉(zhuǎn)（原本{1,2,3,4,5,6}變成{6,5,4,3,2,1}），再把當前的數(shù)組 [0,k) 和 [k,length) 的位置分別進行反轉(zhuǎn)，就這樣，利用三次位置反轉(zhuǎn)，就可以得到數(shù)組向右旋轉(zhuǎn)k位的結(jié)果。
reverse()方法能把傳入的數(shù)組arr的 [start, end] 的位置元素一一調(diào)換。

Java解答如下：

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

    private void reverse(int[] arr, int start, int end) {
        while (start < end) {
            arr[start] = arr[start] + arr[end];
            arr[end] = arr[start] - arr[end];
            arr[start] = arr[start] - arr[end];
            start += 1;
            end -= 1;
        }
    }