504，旋转数组的3种解决方式

Original 山大王wld 数据结构和算法 2022-05-19

收录于合集 #算法图文分析 161个

There are many things that seem impossible only so long as one does not attempt them.

很多事情看起来不可能只是因为没有人尝试过。

问题描述

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

示例 1:

输入: nums = [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:

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

提示：

1<=nums.length<=2*10^4
-2^31<=nums[i]<=2^31-1
0<=k<=10^5

使用临时数组解决

这题是让把数组中的每个元素都往右移动k位。最简单的一种解决方式就是使用一个临时数组解决，先把原数组的值存放到一个临时数组中，然后再把临时数组的值重新赋给原数组，重新赋值的时候要保证每个元素都要往后移k位，如果超过数组的长度就从头开始，所以这里可以使用(i + k) % length来计算重新赋值的元素下标

 1public void rotate(int nums[], int k) {
 2    int length = nums.length;
 3    int temp[] = new int[length];
 4    // 把原数组值放到一个临时数组中，
 5    for (int i = 0; i < length; i++) {
 6        temp[i] = nums[i];
 7    }
 8    // 然后在把临时数组的值重新放到原数组，
 9    // 并且往右移动k位
10    for (int i = 0; i < length; i++) {
11        nums[(i + k) % length] = temp[i];
12    }
13}

部分元素多次反转

还有一种方式就是先反转全部数组，在反转前k个，最后在反转剩余的，如下所示

 1public void rotate(int[] nums, int k) {
 2    int length = nums.length;
 3    k %= length;
 4    //先反转全部的元素
 5    reverse(nums, 0, length - 1);
 6    //在反转前k个元素
 7    reverse(nums, 0, k - 1);
 8    //接着反转剩余的
 9    reverse(nums, k, length - 1);
10}
11
12//把数组中从[start，end]之间的元素两两交换,也就是反转
13public void reverse(int[] nums, int start, int end) {
14    while (start < end) {
15        int temp = nums[start];
16        nums[start++] = nums[end];
17        nums[end--] = temp;
18    }
19}

其实还可以在调整下，先反转前面的，接着反转后面的k个，最后在反转全部，原理都一样

 1public void rotate(int[] nums, int k) {
 2    int length = nums.length;
 3    k %= length;
 4    //先反转前面的
 5    reverse(nums, 0, length - k - 1);
 6    //接着反转后面k个
 7    reverse(nums, length - k, length - 1);
 8    //最后在反转全部的元素
 9    reverse(nums, 0, length - 1);
10}
11
12//把数组中从[start，end]之间的元素两两交换,也就是反转
13public void reverse(int[] nums, int start, int end) {
14    while (start < end) {
15        int temp = nums[start];
16        nums[start++] = nums[end];
17        nums[end--] = temp;
18    }
19}

环形旋转

类似约瑟夫环一样，把数组看作是环形的，每一个都往后移动k位，这个很好理解，画个图来看一下

但这里有一个坑，如果nums.length%k=0，也就是数组长度为k的倍数，这个会原地打转，如下图所示

对于这个问题我们可以使用一个数组visited表示这个元素有没有被访问过，如果被访问过就从他的下一个开始，防止原地打转。

 1public static void rotate(int[] nums, int k) {
 2    int hold = nums[0];
 3    int index = 0;
 4    int length = nums.length;
 5    boolean[] visited = new boolean[length];
 6    for (int i = 0; i < length; i++) {
 7        index = (index + k) % length;
 8        if (visited[index]) {
 9            //如果访问过，再次访问的话，会出现原地打转的现象，
10            //不能再访问当前元素了，我们直接从他的下一个元素开始
11            index = (index + 1) % length;
12            hold = nums[index];
13            i--;
14        } else {
15            //把当前值保存在下一个位置，保存之前要把下一个位置的
16            //值给记录下来
17            visited[index] = true;
18            int temp = nums[index];
19            nums[index] = hold;
20            hold = temp;
21        }
22    }
23}