SilentSpiral

穿针引线

题目: 旋转数组

将包含 n个元素的数组向右旋转 k 步。
例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7]，向右旋转后的结果为 [5,6,7,1,2,3,4]。

  • 注意: 尽可能找到更多的解决方案，这里最少有三种不同的方法解决这个问题。
  • 要求: 空间复杂度为 O(1)

原题链接
嗯我知道你懒得读英文

简要思路

可以从nums[0]开始, 计算当前元素的应移动到的位置
易知 ptr_next = (ptr_now + k) mod n
用一个临时变量保存下一个位置的值, 将当前元素赋给下一个地址
进一步的, 可以用nums[0]代替这个临时变量
这个方法就像在穿针引线一样
但仍面临问题

先从第一位开始穿针
如果n,k互质, 那么一次性能够穿完，岂不美哉
如果不互质，那么需要穿gcd(n,k)次, 因为每次会成一个环路
需要一个变量保存开始穿针的位置
或者更高段位的做法只要next<gcd就结束
考虑n,k互质的情况
只有n,k互质a才能遍历0~n-1
a ≡ m*k mod n
m ≡ a*k-1 mod n
用数论的角度，k是模n的循环群的生成元
这里是证明n,k互质一定能一次穿针引线解决问题的

一次穿针引线遍历的所有点，我们称之为一个环路
(不知道这对应什么代数结构, 想说是群又怕被打脸, 真鸡儿丢人退群退群)

设gcd(k,n)=g, 则k = Ag，n = Bg，gcd(A,B) = 1
mAg ≡ a mod Bg <=> mAg = a+rBg
再同时对B取模得mAg ≡ a mod B
于是有mk ≡ a mod B ……浪费我感情…
目前得到的情报: 每次穿针引线能够遍历B = n/g个点, 即每个环路有B个元素

如果p和q在一个环路里, 那么说明p+mk ≡ q mod n
如果0和1在一个环路里, 就是0+mk ≡ 1 mod n
观察0+mk ≡ 1 mod n这个式子, 好了两边+1
1+mk ≡ 2 mod n,意味着1和2也在一个环路里
2+mk ≡ 3 mod n,意味着2和3也在一个环路里
……
递推一下…所有元素都在一个环路里, 皆大欢喜(大误)
说明假设 [如果0和1在一个环路里] 有时不一定成立

那么有的小学数论已经还给老师的人就要问了:
你同余式两边同时+1s, 会不会不符合基本法
1+mk ≡ 2 mod n等价于1+mk=2+nr
等式两边+1, 再对n取模
抱歉，等式就是可以为所欲为的

那么，1到gcd之间，能不能有两个数属于同一个环路呢？
譬如x和x+r吧，x+r<g
那么x, x+r, x+2r, x+3r, … , x+(n/g)r(都小于n, 不必取模)都属于一个环路了吧

一共(至少)有B+1个元素, 与前述矛盾

我知道你关心什么:
接下来要证明x+(n/g)r<n
　x+r < g　=>　r < g-x
x + nr/g < x + n(g-x)/g = x + n - xn/g = n - x(n-g)/g < n (反正减掉的是个正数)
可以说不等式很松了

代码剽窃自这里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    int gcd(int a,int b){
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
public:
    void rotate(vector<int> &nums, int k) {
        int len=nums.size();
        if(!k || len==k)
            return;
        int groups = gcd(len,k), ptr;
        for (int i = 0; i < groups; ++i) {
            ptr=i;
            do {
                ptr = (ptr + k) % len;
                swap(nums[i], nums[ptr]);
            }while(ptr!=i);
        }
    }
};

但其实这是一种很蠢的方法
惊艳的方法反正我也想不到, 委屈.jpg
譬如:
> 1234567
> 4321 765
> 5671234

就展示这一遍
没看懂的….
翻回去再看谢谢

打赏