环状替换法详解
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
链接：https://leetcode.cn/problems/rotate-array
示例：
输入: 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]
1.在官方解答中给出了环装替换法，不易理解，现给出推导：
⭐ 该方法实质可以理解为：
一个圆形桌子上吃饭，每个人想吃的菜不同，就移一下位置。（假设桌子不能转哈）
一共有n个人，要往自己的左手边移动k个位置坐。
ex1：
对于其中一个元素 x ，间隔k回到自己要走a圈，a为整数；
要么一圈经过个元素呢？ n/k个，对吧.（在这个n/k不一定是整数,但是实际要数那么个数就是向下取整）
例如图1：从0开始，间隔3经过了 3和6 。个数为7/3，取整为2
假设x回到自己身上一共经过b个元素，b也是整数。
那么
\[a*\frac{n}{k} = b \]注意：a是整数，b也是整数.
但是！注意了轰！n/k不一定是整数.
\[a*\frac{n}{k} 是整数，a又是最小的圈数，所以a=\frac{k}{gcd(k,n)} \]\[为啥是\frac{k}{gcd(k,n)}呢？n=gcd(k,n)*m,k=gcd(k,n)*h \]\[\frac{n}{k}也就是\frac{m}{h},m和h不可约，那么a=h=\frac{k}{gcd(k,n)}时最小 \]所以：
\[遍历次数为：\frac{n}{b}=\frac{n}{a*\frac{n}{k}}=gcd(n,k) \]所以遍历次数gcd(n,k)
2.C++代码如下
class Solution {
public:
void rotate(vector<int>& nums, int k) {
if (k == 0)
return;
int N = nums.size();
k = k % N;
int j;
int Num = gcd(N, k);
for (int i = 0; i < Num; ++i)
{
j = i; //记录起点
do
{
j = (j + k) % N;
Swap(nums[i], nums[j]);
} while (j !=i ); //判断有没有回到原来的位置
}
}
void Swap(int& x, int& y)
{
int temp = x;
x = y;
y = temp;
}
//求最大公约数
int gcd(int a, int b)
{
int temp;
if (a < b)
Swap(a, b);
while (b>0)
{
temp = a % b;
a = b;
b = temp;
}
return a;
}
};
比如图1：0-3-6-2-5-1-4-0
其实就是每次进行交换，0号说我要坐3号位置，那么3号说我让给你你吧，我先坐0号。
但是3号自己也要动，所以3号又从0号坐到了6号
标签：frac,gcd,temp,nums,int,替换法,整数,详解,环状 From： https://www.cnblogs.com/Kellen-Gram/p/17404563.html