[数据结构与算法]力扣之轮转数组（玩转取余操作）

• 我的超时方法，理解起来非常简单，就是一次只往右挪一位，循环k次就好
• 我还想了一个方法和答案第二种环转方法类似，但是咋都不对，下面重点讲一下这个，这个方法比较难，答案还用到了高代里的一些结论，但是作为数学组选手，俺就喜欢挑战这种方法

环转替代法

• 好家伙，那答案写的，我看了俩小时都没懂，结果看到一个圆圈，突然就理解了
• 这道题的解题关键就是得知道遍历次数，啥叫遍历次数呢？简单来说就是圈圈个数，这里的圈必须首尾一致，比如下面这个例子，圈圈个数是2（1351和2462）
• 
• 答案里得到遍历次数的公式太牛啦太牛啦，这不看答案怎么知道啊？
• 关键公式$an=bk$
  • $a$是圈数，即完成一次遍历要绕数组几圈。$n$是整个数组的长度，$b$是每次遍历的元素个数，比如上个例子里的$b=3$，$k$就是往右行走的步数（题目给的）
  • 这个公式咋来的呢，力扣的官方解释一开始我没看懂，但结合圆圈来理解就非常清晰了
  • 
    • 这里a=1,n=6,k=2,b=3
  • 再来个例子
    • 这里a = 2,n=3,k=2,b=3
  • 所以$an=bk$的解释就是遍历一次走过的距离
    • $an$是根据转圈数得到，因为首尾一致，肯定是圈，每个圈又有n个元素
    • $bk$是根据遍历的元素×迈开步子的长度
• 以上证明了$an=bk$成立的合法性，接着要求$b$的大小了，因为只要求得b的大小，就能求遍历次数$=\frac{n}{b}$，这个公式应该好理解，只要认同每个遍历都包含相同的元素个数即可
• 现在已知得到是$n,k$，怎样能不通过$a$来求$b$呢？高级的知识点来了：$an$肯定是$n$的倍数毋庸置疑，$an$也是$k$的倍数这也毋庸置疑，然后肯定要$a$取最小，是可以无限转圈，但俺们要求用最小的圈数回到原点，所以可以得到$an=lcm(n,k)$，即$an$是$n,k$的最小公倍数
• 因此就有$$b=\frac{an}{k}=\frac{lcm(n,k)}{k}$$
• 于是数组一共要遍历的次数为$$\frac{n}{b}=\frac{nk}{lcm(n,k)}=gcd(n,k)$$
  • $gcd$是最大公约数
  • 解释一下这个式子，为什么$nk$除以最大公倍数就等于最小公约数了呢，高代里有证明啊，可以去看，直观可以这么理解
  • (nk/nk的最大公约数gcd)保证了这个数被拆解成质数的乘积里，肯定没有重复的数,这不就是最大公倍数嘛！
• 然后在每个遍历里，每个位置的元素都有自己想要去的地方，同时每个位置又都被其他位置的元素惦记
• 所以指定一个temp/prev，表示某个位置要出去的那个值，比如0位置的元素要出去找下家了，temp=nums[0]=1,那哪位下家能取这个值呢，是$x=(0+k)\mathrm{m}\mathrm{o}\mathrm{d}n$呐，于是$nums[x]=temp$
• 然后就是要得到遍历停止的条件了，这里的遍历停止指的是一个圈结束哈，标记开始的位置$start$,记录现在的位置$current$，当$current=start$时，一次遍历结束
• 直接看代码吧

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        count = gcd(n,k)
        start = 0        
        for start in range(0,count):
            #这里容易出错，没有取余运算的话可能会出现current>n-1的情况
            current = (start+k)%n
            prev = nums[start]
            while current!=start:
            	#python里的swap就是这么简单粗暴
                nums[current], prev = prev,nums[current]              
                #这一步是最妙的，一个式子实现完美转圈圈，我竟然还分了两种情况0~k-1和k~n-1
                current = (current+k) % n
            nums[start] = prev 

数组翻转法

• 最简单，没有什么深度理解的地方，就是翻转3次
• 
• 关于翻转的代码可以看一下，指定两个指针，start和end，从左右往中间夹击
  C++代码

class Solution {
public:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }

    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};