题解 | #旋转数组#

旋转数组，完全基于两两交换实现数组移位，时间O(n)，空间O(1)

思路：不断让前m和尾m个元素交换，维护一个指针start，它是交换完元素的终点，未交换元素的起点。每交换完成m个元素，start往右移动m。要注意的边界条件是，当start靠近尾部时，交换区间会重叠，此时交换之后，重叠区域会被错误的交换到末尾。就需要把重叠区域移到start后，问题就从原来的把末尾m位移动到start后变成了把重叠区域移动到start后，即m=len(重叠区域)。继续交换，直到start+m越界。

class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        m = m % n     # m与m % n结果相同
        start = 0     # start 左边都是排好序的
        while m and start+m < n:
            for i in range(m):
                a[start+i], a[n-m+i] = a[n-m+i], a[start+i] # start开始的前m与后m交换
            start += m
            if m > n - start:  # 靠近末尾交换长度不够，有重叠
                m = m - (n - start)   # 减少交换长度为重叠区域长度
        return a