刷题之旅从数组类型的题目开始。第十四道题目是旋转数组，对应leetcode的题号为189。

image

题目描述

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

示例 1:

1
2
3
4
5
6
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

1
2
3
4
5
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:

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

解题思路

第一个思路是我以前用的，就是要求循环数组，那么就可以变换思路：

比如数组为[1,2,3,4]

我组装新的数组：[1,2,3,4,1,2,3,4]

那么k=0时对应的是[1,2,3,4]，那么从index=(4-0)处开始读取，所以还是[1,2,3,4]；

k=1时对应的是[4,1,2,3]，那么从index=(4-1)处开始读取，所以是[4,1,2,3]；

…

当k=4的时候，又跟k=0的情况一样了，那么其实k=4i的时候都跟k=0一样，k=4i+1的时候都跟k=1一样，所以计算的时候对k%length一下就是通用情况了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public void rotate(int[] nums, int k) {
        //新建一个长度为两倍的数组，存储两个nums，循环k个其实就是从这大数组中寻找对应的位置读取出来即可
        int[] temp = new int[nums.length*2];
        for(int i=0;i<temp.length;i++){
            temp[i] = nums[i%nums.length];
        }
        //由于k其实是一个循环的数字，比如数组长度为4时，k=1和k=5效果是一样的，所以我只计算一种情况即可
        int index = nums.length-k%nums.length;
        int j = 0;
        //开始赋值，读取指定的数组区间的数字就是我们需要的数组序列
        for(int i=index;i<nums.length+index;i++){
            nums[j++] = temp[i]; 
        }
    }
}

此方法

1
2
执行用时 :1 ms, 在所有 Java 提交中击败了81.21%的用户
内存消耗 :37.8 MB, 在所有 Java 提交中击败了92.59%的用户

不过题目最后说有很多种算法，尤其是原地算法，上一种算法开辟了一个新数组，因此还需要想想办法如何原地实现。

假设 n=7n=7 且 k=3k=3 。

1
2
3
4
原始数组                  : 1 2 3 4 5 6 7
反转所有数字后             : 7 6 5 4 3 2 1
反转前 k 个数字后          : 5 6 7 4 3 2 1
反转后 n-k 个数字后        : 5 6 7 1 2 3 4 --> 结果

规律就是：先反转整个数组，然后反转前面k个，最后反转最后n-k个，即可返回会最终的结果。

1
2
执行用时 :1 ms, 在所有 Java 提交中击败了81.21%的用户
内存消耗 :37.3 MB, 在所有 Java 提交中击败了95.41%的用户

代码如下：

提交代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        nums = reverse(nums,0,nums.length-1);
        nums = reverse(nums,0,k-1);
        nums = reverse(nums,k,nums.length-1);
    }

    private int[] reverse(int[] nums,int start,int end){
        while(start < end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
        return nums;
    }
}