题解 | #旋转数组#

i 移动到 i+m，就是让a[i+m]=a[i]，需要注意 i+m 是否越界了，如果越界了，就减去 n。同时要保存a[i+m]的值，然后i 变成 i+m，然后一直重复这个操作就可以。但是要注意，如果 m 和 n 不是互质的，最大公约数为maxcom，则 i 和 i+m 一定是0或maxcom的倍数。移动了n / maxcom后，下标为maxcom整数倍的数组已经在正确的位置，之后移动下标对maxcom取余为1到maxcom-1的下标。

from posix import major
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 旋转数组
# @param n int整型 数组长度
# @param m int整型 右移距离
# @param a int整型一维数组 给定数组
# @return int整型一维数组
#
class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        # write code here
        m1 = m
        if m > n:
            m1 = m - int(m / n) * n
        if m1 == 0:
            return a
        # 求最大公约数为maxcom
        maxcom = self.maxCommon(n,m1)
        for j in range(0,maxcom):
            index1 = j
            x1 = a[j]
            x2 = a[j]
            for i in range(int(n / maxcom)):
                index2 = index1 + m1
                if (index2 + m1) >= n:
                    index2 = index2 - n
                x2 = a[index2]
                a[index2] = x1
                x1 = x2
                index1 = index2
        return a
    def maxCommon(self, n, m) -> int:
        if n % m == 0:
            return m
        c1 = min(m, n - m)
        c2 = n % c1
        while c2 != 0:
            n = max(c1, c2)
            m = min(c1, c2)
            c1 = min(m, n - m)
            c2 = n % c1
        return c1