从0开始的秋招刷题路，记录下所刷每道题的题解，帮助自己回顾总结
189. 轮转数组
给定一个整数数组 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]
提示：
1 <= nums.length <=
1
0
5
10^5
105
−
2
31
-2^{31}
−231 <= nums[i] <=
2
31
−
1
2^{31} - 1
231−1
0 <= k <=
1
0
5
10^5
105
进阶：
尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
思路
从nums[0]开始，放到该数的新位置(0 + k)，然后再寻找该位置值的新位置，直至回到0时结束。 但是该方法不能保证遍历完所有的位置，如 7 位的数组后移3个位置只需遍历一遍，而 6 位的数组后移4个位置需要遍历两遍（再从i = 1开始）。 可以发现这个遍历的次数就是数组长度和k的最大公约数。文章来源：https://www.toymoban.com/news/detail-415163.html
代码文章来源地址https://www.toymoban.com/news/detail-415163.html
public void rotate(int[] nums, int k) {
int len = nums.length;
for (int i = 0;i < gcd(k, len);i++){
int idx = (k + i) % len, num = nums[i];
while (idx != i){
int item = nums[idx];
nums[idx] = num;
idx = (idx + k) % len;
num = item;
}
nums[i] = num;
}
}
private int gcd(int a, int b) {
return a % b == 0 ? b : gcd(b % a, a);
}
到了这里，关于Leetcode力扣秋招刷题路-0189的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
