189. 旋转数组

题目

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
进阶：

  • 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

示例 1:

  1. 输入: nums = [1,2,3,4,5,6,7], k = 3
  2. 输出: [5,6,7,1,2,3,4]
  3. 解释:
  4. 向右旋转 1 步: [7,1,2,3,4,5,6]
  5. 向右旋转 2 步: [6,7,1,2,3,4,5]
  6. 向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

提示：

  • 1 <= nums.length <= 2 * 104
  • -231 <= nums[i] <= 231 - 1

  • 0 <= k <= 105

    题解

    最直观的方案：

  • 将 a[i] 移动到 a[i+k]

  • 将 a[i+k] 移动到 a[i+2k]
  • …
  • 直到全部移动了一遍

那么移动的次数是多少呢?
假设数组长度为 m，移动步长为 k，那么只需求得最小的 n 使得 nk%m==0 即可。
很显然：nk 为 m 和 k 的最小公倍数 lcm(m,k)，首先我们知道：
189. 旋转数组 - 图1
所以有：
189. 旋转数组 - 图2
本质上来说，m 在对 k 取余的情况下，被分成了 gcd(m,k) 个等价类，每个等价类中有 m/gcd(m,k) 个元素。
我们只需在每个同余等价类中交换顺序即可。
此外，交换顺序时还有个小技巧：把数组全向右移等价于向左两两交换。
举个例子：
如果我们想把 1,2,3,4 变成 4,1,2,3，那么可以像下面这样，将 * 处的两个元素互换位置。

1,2,3,4
*     *
4,2,3,1
    * *
4,2,1,3
  * *
4,1,2,3

那么代码就很简单了：

import math
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        m = len(nums)
        g = math.gcd(m, k)
        for i in range(g):
            j = i
            for _ in range(m//g-1):
                nums[j], nums[(j-k) % m] = nums[(j-k) % m], nums[j]
                j = (j-k) % m

image.png