前言

今天这道题难度是中等的

题目

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

示例 2:

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

进阶：

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

分析

我们直接来看进阶的第二点，采用空间复杂度为O(1)的方式，也就是直接操作在原有数组中

这里有个点我之前一直没说，就是一维结果的数组，那么时间复杂度应该小于等于O(n)，所以一般我们得思考一个一次遍历的方式。

这道题其实很简单，就是一个从头出，然后从尾巴进入的方式，所以解法也很简单

解

取余是为了拿到最小移动的次数，因为等于len的时候就不需要动。

按理说这个解法时间复杂度应该是最小的了，但是提交的时候耗时需要359ms。。。应该是insert会影响整个数组下标的更新，所以需要大量的耗时。

所以我们来采用别的方案来优化下

优化

其实这道题还有个很巧妙的解法，就是切割，切片成等长的不同组。

然后组里的元素和不同组同位置的元素轮换即可。

这里可能有些费解，我们来个例子分析下：

nums = [-1, -100, 3, 99, 88, 2333], k = 4。

它的正确输出是：

[3, 99, 88, 2333, -1, -100]

我们要怎么切呢？

根据k来切，如果k不能整切，那么就取数组长度和k的最大公因数，这样必定可以整切

比如我们的这个例子，它不能整除4，所以要取长度6和4的最大公因数，也就是2来切。

所以这个数组最终被切割为[-1, -100], [3, 99], [88, 2333]。

那么我们要处理这些组的时间复杂度就是O(2 * 3)，因为每个元素需要轮换3次,而每组只有俩元素

所以我们可以直接开始写代码了

先来实现获取最大公因数的：

用循环或者递归都行。

然后我们来实现主体：

这里没啥好说的了

测试用例

总结

虽然我们pop和insert需要遍历的次数最少，但是我们耗时却很高，因为insert是插入到第一个元素，会影响到整个数组的下标更新，所以存在较高的耗时。

第二种方法需要我们脑子绕下弯，还是那句话，这种东西得有数理思维，没有，可能就绕不过去了。。。。