旋转数组

题目地址：https://leetcode-cn.com/problems/rotate-array/

给定一个数组，将数组中的元素向右移动 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) 的 原地 算法。

题目信息

输入：数组nums、整数k

输出：修改数组（nums向右移动k位）

额外条件：空间复杂度O(1)

思考

首先想到的就是直接设置最终值，原地修改数据会丢失所以添加备份变量backup。备份值即原先值在移动时也需要与目的地数组值做交换则再需要一个中间值temp

以示例1数组演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[1,2,3,4,5,6,7] k=3
//先原第1位移动三位到第4位
[1,2,3,1,5,6,7] backup = 4
//再移动原第4位值移动到第7位
[1,2,3,1,5,6,4] backup = 7
//再移动原第7位值移动到第3位
[1,2,7,1,5,6,4] backup = 3
//再移动原第3位值移动到第6位
[1,2,7,1,5,3,4] backup = 6
//再移动原第6位值移动到第2位
[1,6,7,1,5,3,4] backup = 2
//再移动原第2位值移动到第5位
[1,6,7,1,2,3,4] backup = 5
//再移动原第5位值移动到第1位
[5,6,7,1,2,3,4] backup = 1

最后循环到设置第一位，结束所有值移动完毕。

但这样的过程其实有个问题，并不是所有的情况都能一次循环移动所有元素。举两个例子：

示例一的情况一次循环就移动的所有元素，但上面两个例子从第一位出发到最后设置第一位完成循环但并没有设置完所有元素。一个要用两次循环一个三次。这样去使用一个中间变量去循环设值需要多少个循环取决于数组长度与k的最大公约数。

这样思路大体形成，是一个双循环。那么找到双循环的出循环条件，小循环结束条件则是下一步要移动的元素索引就是环状替换的开始索引，条件比较即使用while循环。外层循环条件两种方式都可以解决一种就是得到length与k公约数，第二种使用count计数，由于最后是数组元素全部移动所以会移动length次，小循环里每完成一次设值count累加，小循环完后来到外层循环如果count小于length则还有下一组循环。全部完成最终count是一定等于length的，出循环结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
//这里提供一个求最大公约数的辗转相除法
int maxNumber(int m, int n) {
    int temp;
    if (n > m) {
        temp = n;
        n = m;
        m = temp;
    }
    if (m % n == 0) {
        return n;
    }
    return maxNumber(n, m % n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void rotate(int[] nums, int k) {
    int len = nums.length;
    for(int start = 0; start < maxNumber(len,k); start++){
        /*
        设置当前元素索引
   		将当前元素备份
        */
        int current = start;
        int backup = nums[current];
        do{
            //计数最终移动的索引
            int next = (current + k) % len;
            //当前元素原来值backup与目的地元素交换
            int temp = nums[next];
            nums[next] = backup;
            backup = temp;
            //交换完毕更新当前索引
            current = next;
        }while(start != current);
    }
}

上面外循环以公约数为条件即已知循环次数完成，下面使用count在小循环里计数在外循环判断完成

方式一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void rotate(int[] nums, int k) {
    int count = 0;
    int len = nums.length;
    for(int start = 0; count < len; start++){
        int current = start;
        int backup = nums[current];
        do{
            int next = (current + k) % len;
            int temp = nums[next];
            nums[next] = backup;
            backup = temp;
            current = next;
            count++;
        }while(start != current);
    }
}

这样环状替换的解决方式是最先想到的，还有一种方式看题目示例就可以get到这个方向。也就是解决整体移动一次的逻辑，接下来就是循环就完了。整体移动一次时间复杂度就为n然后完成n次。比上面的算法就复杂度来看差一些。完成整体移动一次使用交换法即可（用备份值方式仅仅多了变量不会影响时间复杂度）。

1
2
3
4
5
6
//每次使用最后位与i位进行交换，i++
[1,2,3,4,5]   1<==>5
[5,2,3,4,1]   2<==>1
[5,1,3,4,2]   3<==>2
[5,1,2,4,3]   4<==>3
[5,1,2,3,4]   
1
2
3
4
5
for (int j = 0; j < len; j++) {
    temp = nums[j];
    nums[j] = nums[len-1];
    nums[len-1] = temp;
}

那么有了这样一个移动一次的代码，再结合K外层循环

方式二

1
2
3
4
5
6
7
8
9
10
public void rotate(int[] nums, int k) {
    int temp;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < nums.length; j++) {
            temp = nums[j];
            nums[j] = nums[nums.length-1];
            nums[nums.length-1] = temp;
        }
    }
}

最后还有一个反转法，跳开设置值的思路，通过别的算法组合也能达到目标情况，在初高中数学当中也是常常有知道一个式子的值求一个很长的式子而不用把第一个式子解开而是将最终式子化成已知式子的组合最终简单求解。在这里也是一样一个反转算法这样的算法很简单

1
2
3
4
5
6
7
8
while (i < j) {
    int temp = nums[i];
    nums[1] = nums[j];
    nums[j] = temp;
    i++;
    j--;
}

观察我们的要得到的一个结果

1
2
3
//nums = [1 2 3 4 5 6], k=3
1 2 3 4 5 6
4 5 6 1 2 3

可以通过反转的组合实现

1
2
3
4
1 2 3 4 5 6
6 5 4 3 2 1  全反转
4 5 6 3 2 1  0到k-1反转
4 5 6 1 2 3  k到len-1反转

这样就有新的方式解决，远远比直接带值要快（人脑层面），时间复杂度当然还是和方法一是相同的

方式三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

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