每日一题-轮转数组

1. 题目描述

题目链接: 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 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]

2. 使用额外的数组

一种比较简单的方法，是创建一个新的数组，将原数组的元素按照旋转后的位置依次放入新数组中。这种方法需要O(n)的额外空间，其中n是数组的长度。

下面是一个详细说明和示意图，演示如何使用额外的新数组来实现数组向右旋转。假设我们有一个数组 nums = [1, 2, 3, 4, 5, 6, 7]，要将其向右旋转3个位置（k=3），我们将创建一个新数组 new_nums，并按照旋转后的位置依次将元素从原数组中放入新数组中。

创建一个新数组 new_nums，与原数组 nums 同样大小，初始都为0：

原数组：  [1, 2, 3, 4, 5, 6, 7]
新数组：  [0, 0, 0, 0, 0, 0, 0]

遍历原数组 nums 中的每个元素，将元素按照旋转后的位置放入新数组 new_nums 中。为了确定每个元素的新位置，我们可以使用以下公式：新位置 = (当前位置 + k) % 数组长度。 当前例子中，k=3，数组长度为7。

开始遍历，第一个元素1的新位置为 (0 + 3) % 7 = 3，所以将1放入新数组的第3个位置：

原数组：  [1, 2, 3, 4, 5, 6, 7]
新数组：  [0, 0, 0, 1, 0, 0, 0]

第二个元素2的新位置为 (1 + 3) % 7 = 4，所以将2放入新数组的第4个位置：

原数组：  [1, 2, 3, 4, 5, 6, 7]
新数组：  [0, 0, 0, 1, 2, 0, 0]

继续这个过程，将所有元素按照新位置放入新数组：

原数组：  [1, 2, 3, 4, 5, 6, 7]
新数组：  [5, 6, 7, 1, 2, 3, 4]

最终旋转完成，将新数组 new_nums 的数据拷贝到原数组当中即可:

原数组：  [5, 6, 7, 1, 2, 3, 4]
新数组：  [5, 6, 7, 1, 2, 3, 4]

这个过程中，我们创建了一个新数组，并根据旋转后的位置依次将原数组的元素放入新数组。这种方法需要O(n)的额外空间，其中n是数组的长度

3. 数组翻转

这道题是将数组中的元素从一处移动到另一处，通常可以考虑反转这一操作，因为反转是可逆的。在向右旋转问题中，我们可以将旋转操作看作是将数组分为两部分，然后将这两部分交换位置。反转这两个部分的顺序就可以实现向右旋转。

这里通过数组翻转来实现向右旋转时，可以通过三次翻转操作来完成。这个方法不需要额外的数组空间，只需要在原数组上进行操作。下面详细说明其中的过程，假设有一个数组 nums = [1, 2, 3, 4, 5, 6, 7]，要将其向右旋转3个位置(k=3):

首先，将整个数组翻转。这将把数组的最后k个元素移到数组的前面:

原数组：  [1, 2, 3, 4, 5, 6, 7]
翻转后：  [7, 6, 5, 4, 3, 2, 1]

此时，数组的前3个元素是原数组的最后3个元素，接下来，翻转前k个元素。这将把原数组的最后k个元素移动到数组的末尾。

前k个元素： [7, 6, 5]
翻转后：    [5, 6, 7]

此时，数组的前3个元素是原数组的最后3个元素，而数组的剩余部分是原数组的前面部分。最后，翻转剩下的元素（原数组的前n-k个元素），将它们移动到正确的位置。

剩余的元素： [1, 2, 3, 4]
翻转后：    [4, 3, 2, 1]

此时，数组的前3个元素是原数组的最后3个元素，数组的剩余部分是原数组的前面部分。旋转完成，数组中的元素已经按照要求向右旋转3个位置。

最终结果： [5, 6, 7, 1, 2, 3, 4]

通过三次翻转操作，我们成功地将原数组向右旋转了3个位置，而且没有使用额外的数组空间。这个方法是一个高效且常用的旋转数组的方式。

4. 环形替换

将数组看作一个环，从第一个元素开始，计算每个元素在旋转后的位置，然后将元素替换到该位置，直到处理完所有元素，这个过程可能需要经过多轮循环。下面我们来展示下每轮循环的具体流程。

假设我们有一个数组 nums，以及需要将它向右旋转k个位置，其中k等于3。数组 nums 如下：

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

我们将按照下面的步骤开始移动元素：

1. 选择一个起始位置，通常从数组的第一个元素开始，即 nums[0]。
2. 获取到其最终所在位置，根据旋转的规则来获取。对于向右旋转，下一个位置是当前位置加上k，即 0 + 3 = 3。
3. 保留该位置的数据(nums[3]，即4)，然后将 nums[0] 的数放到下标等于3 的位置下。
4. 继续移动到下一个位置，根据旋转规则，下一个位置是 3 + 3 = 6，此时6 大于数组长度，需要取余数组长度，此时获取到0, 将之前保留的nums[3] 的数据赋值到nums[0] 当中。
5. 发现回到原点位置，此时完成一轮循环。

这个过程的图示如下：

初始状态: [1, 2, 3, 4, 5, 6]
第一步:    1   2   3   4   5   6
           ↓
第二步:    1   2   3   1   5   6
               ↓
第三步:    4   2   3   1   5   6

通过一轮循环，能够将部分数据成功放置到正确的位置下。这里我们需要证明下，从原点出发后，经过一轮循环，再次回到原点的过程中，中间会不会经过相同的下标。因为每经过一个下标，都会将该元素放到正确的位置，如果重复到达，此时是有问题的。

这里我们可以使用数据归纳法，来证明遍历的过程是不会重复到达某个数组下标位置的，除非回到了开始的地方。假设我们在环形数组中每次向前走k步，但不回到原点。现在我们使用数学归纳法来证明，如果我们在某一步重复达到了某个位置p，并且之前没有回到原点，那么前一个位置p-1也一定重复到达了，以此类推，最终说明第一个重复到达的点肯定是原点。

但是一次循环，并不一定能够经过所有的元素。下面我们需要去获取到每次循环能够到达的元素的数量，从而获取到需要循环遍历的次数。

每次从起点出发，绕行一圈，再次回到原点的过程中，其经过的元素的个数可以通过下面公式来获取到，公式如下:

(kx + i) % n = i 

为什么是这条公式呢? 因为回到原点，说明是经过的长度必须是数组长度 n 的整数倍，经过的长度用kx来表示, k 代表每次移动的步数，而x代表移动的次数。

而 kx 是 n 的整数倍的数有无数个，我们只需要第一次到达原点时所需要移动的步数，需要获取到kx 的最小值。因此kx 应该是x 和 k 的最小公倍数，这里最小公倍数用LCM来表示。

因此，每次移动元素的个数为 x = (LCM(k,n)/k)，其中参数k 和参数n 都是已知的，基于此能够获取到每次移动元素的个数。下面举个例子来说明一下，数组如下:

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

数组需要向右轮转2个位置，此时k = 3， n = 6, 基于此获取到最小公倍数 = 6。基于公式x = (LCM(k,n)/k)，可以获取到每次循环移动元素的个数，这个例子中，每次循环移动元素的格式为2。

循环的次数，为n / x, n 代表数组的长度，x 代表每次循环移动元素的数量。然后每次循环的开头，都是从上一次循环的起点的后一个元素出发的。 通过这n / x 次的循环，就可以将所有数据移动到正确的位置。

因此，在这道题中，如果我们使用环形替换，此时需要先计算出最小公倍数LCM(k,n), 然后再基于公式LCM(k,n)/k 获取到每次移动元素的个数，然后再通过n / 每次移动元素个数 获取到需要循环的次数，公式可以按照下面流程来进行转换:

循环次数 = n / (lcm(k,n) / k) = nk / lcm(k,n) =  gcd(n,k)

其中gcd(n,k) 代表 n 和 k 的最小公约数。每次循环中，就从某个起点出发，将数据移动到目标位置。

下面我们通过一个完整的例子，展示整个流程，首先数组如下：

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

通过上面gcd(n,k) 公式计算，获取到最大公约数为3,此时需要进行三轮循环。

开始第一轮移动，起点坐标为0, 目标下标为3 , 此时将nums[0] 的数据放到nums[3] 下面；第二步则将原本nums[3] 的元素进行移动，将其放到 (3+3) % 6 = 0的位置下，接下来发现已经回到原点，结束第一轮循环，如下:

初始状态: [1, 2, 3, 4, 5, 6]
第一步:    1   2   3   4   5   6
                     ↓
第二步:    1   2   3   1   5   6
          ↓     
第三步:    4   2   3   1   5   6

开始第二轮移动，本次起点坐标为1 , 目标下标为 4 , 此时将nums[1] 的数据放到nums[4] 下面；第二部将原本nums[4] 的元素进行移动，将其放到(4+3) % 6 == 1 的位置下。此时又回到了原点，结束了第二轮循环，具体流程如下:

初始状态: [4, 2, 3, 1, 5, 6]
第一步:    4   2   3   1   5   6
                          ↓
第二步:    1   2   3   1   2   6
              ↓
第三步:    4   5   3   1   2   6

开始第三轮移动，本次起点坐标为2 , 目标下标为 5 , 此时将nums[2] 的数据放到nums[5] 下面；第二部将原本nums[5] 的元素进行移动，将其放到(5+3) % 6 == 2 的位置下。此时又回到了原点，结束了第三轮循环，具体流程如下:

初始状态: [4, 5, 3, 1, 2, 6]
第一步:    4   5   3   1   2   6
                              ↓
第二步:    1   2   3   1   2   3
                  ↓
第三步:    4   5   6   1   2   3

此时经过几轮循环，成功将数据放置到正确的位置，此时时间复杂度为O(n),空间复杂度为O(1)。

5. 总结

上面描述了轮转数组这道题的三种解法，包括使用额外数组，反转数组，环形替换这三种方法，同时也展示了各个解法过程中数据的流转的顺序，希望对于理解该题能够起到积极的作用。 代码已经上传到 github 上，有兴趣可以看看。

本文由博客一文多发平台 OpenWrite 发布！