这篇证明当初做完题就该写了,我太懒了,留了个坑,两周了才来补全。

Problem

189. Rotate Array

Proof

把数组元素个数记为 nn,旋转数目记为 kk,我们对这个题目的思路是可以先把位置 ii 的元素放入到 (i+k)modn(i+k) \bmod n 的位置,这样此位置的原元素会被逐出,我们再把逐出的元素放到它该去的位置即 ((i+k)modn+k)modn((i+k) \bmod n + k) \bmod n 下标处。这样一直进行下去,最终会不会绕一圈即目标位置刚好是 ii 呢。这是肯定的。我们把这期间经历的步数记为 mm。则有:

nj=1mcoeffj=mk(1)n\sum_{j=1}^{m}coeff_{j}=mk \tag{1}

这玩意儿咋得来的。其实很简单,下标 ii 的元素其目标位置是 (i+k)modn(i+k) \bmod n(i+k)modn(i+k) \bmod n 元素的目标位置是 (((i+k)modn)+k)modn((i+k) \bmod n)+k) \bmod n,以此类推,我们不断进行模运算,直到 mm 次后目标位置又变成了 ii

((((((i+k)modn)+k)modn)+k)modn)...=i((((((i+k) \bmod n) + k) \bmod n) + k) \bmod n)...=i

例如当 m=3m=3 时,上式实例化为

(((((i+k)modn)+k)modn)+k)modn=i(((((i+k) \bmod n) + k) \bmod n) + k) \bmod n = i

反向算回去即

i+ank+bnk+cnk=in(a+b+c)=3k其中abc是整数系数,3是系数个数,也是运算步数,即m直接一推广就是(1)i+an-k+bn-k+cn-k=i \\ 即 \\ n(a+b+c) = 3k \\ 其中 a、b、c 是整数系数,3 是系数个数,也是运算步数,即 m \\ 直接一推广就是 (1) 式

在运算过程中,如果步数 m=nm=n,说明我们触及到了每一个元素,即整个数组运算完成。如果不等于,那就说明有元素无法触及到,比如 4 元素的数组,旋转个数为 2,则 1 和 3 下标元素无法触及,根本原因就是此时的 m=2m=2 而不是 4。

但是这种无法触及的现象并不总会发生,比如对于 7 个元素的数组,当k{1,2,3,4,5,6}k \in \left \{ 1,2,3,4,5,6 \right \}时,m都等于7,但当k=7k=7时,m就是2了,于是有5个元素无法触及。

其实对于(1)(1)式来说,不管n和k是多少,我们都可以通过构造m和系数集合让等式成立,并且当m取某些值时,有些元素还会无法触及。注意到这一点,我们在写代码时就有两点需要注意,第一是我们用一个计数变量count来记录有多少个元素被触及了,当count==n时说明任务完成,所有元素均已归位。第二点我们要在每次绕圈开始时要把起点元素记下来,让这个圈绕回来时我们就能检测到,从而让起点加一让算法继续,而不是在这里绕着一个圈子死循环。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
start = 0
n = len(nums)
count = 0
while count < n:
i = start
cur = nums[i]
while True:
bak = nums[(i+k)%n]
nums[(i+k)%n] = cur
cur = bak
i = (i+k)%n
count += 1
if i == start:
break
start += 1