旋转数组

旋转数组_牛客题霸_牛客网

问题简述

一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？
要求：空间复杂度 O(1)，时间复杂度 O(n)

思路

• 根据移动规则，实际上每个数的最终位置是可以确定的；

• 通过取模操作顺序遍历整个数据即可，核心操作：

  nxt = (cur + m) % n
  tmp, a[nxt] = a[nxt], tmp
  cur = nxt

• 注意：

  • 当 m > n 时，m = m % n；

  • m == 0 时，直接返回；

  • 当 m 整数 n 时，会遇到“循环”，即 nxt == start，此时可以从 nxt + 1 重新开始；总遍历次数为 n 次；详见代码；

Python

class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        m = m % n
        
        if m == 0: return a
        # return a[(n-m)%n:] + a[:-m%n]
        
        start = cur = 0
        tmp = a[start]
        for _ in range(n):  # 循环 n 次
            nxt = (cur + m) % n  # 下一个位置
            if nxt == start:  # 遇到循环
                a[nxt] = tmp
                start = cur = nxt + 1
                tmp = a[start]
                continue
            tmp, a[nxt] = a[nxt], tmp
            cur = nxt
            
        return a