题目

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

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

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

解题方法

k次循环

最次的办法可以经过k次循环达到旋转数组的目的，通过一个tmp变量保存数组最后一个元素，每次循环将数组向右旋转一位，经过k次循环便可以达到将整个数组向右旋转k位的目的。然而这种方法效率极低，时间复杂度为O(k*n)，跑了132ms，只超过了17%的java提交，相当差劲。

class Solution {
    public void rotate(int[] nums, int k) {
        // Method_01
        k = k % nums.length;
        while (k-- > 0) {
            int tmp = nums[nums.length - 1];
            for (int j = nums.length - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = tmp;
        }
    }
}

k缓冲数组

通过上面的最次的方法稍加改进便能得到不错的优化，上面的方法只采用了一个变量进行缓冲保存在右移时被前面元素冲掉的元素，这时如果直接使用一个k个长度的缓冲数组来保存数组后k个元素，则只需要进行一次循环，将前面的n-k个元素右移k位，然后将缓冲数组里的元素复制到原数组前k位中，便可以达到数组右移k位的目的。这种方法时间复杂度为O(n+k)，跑了1ms。

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

结语

哈哈，今天看到一句话，“命是弱者的借口，运是强者的谦辞。”Keep coding！

这是笔者刷leetcode的开始，代码都托管在我的Github上，有兴趣的朋友可以相互交流，请多多指教。