最近在LeetCode网站上学习算法,记录一下学到的东西。

##问题描述

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

##解法一:一个一个地移动 刚开始看到这道题,题目说有很多种解法,当时我的第一个想法就是一个一个地移动。于是就有下面的解法:

void rotate(int nums[], int n, int k) {
    int cursor = 0;
    for (int i = 0; i < k; ++i) {
        cursor = nums[n - 1];
        for (int j = 0; j < n - 1; ++j) {
            nums[n-j-1] = nums[n-j-2];
        }
        nums[0] = cursor;
    }
}

这个算法的时间复杂度是O(n*k),空间复杂度是O(1)。提交的时候超时了,So,不能用这种方法。

##解法二:杂耍算法 这个算法是比较难想到的,这个算法优点是在执行了GCD(n, k)次后即可停止,程序的走向我是明白的,至于为什么能够如此,还是上网查了很多资料才弄明白了,现在通过自己的语言描述一遍。加深理解。

GCD(Greatest Common Divisor)–最大公约数

###辗转相除法求最大公约数。 两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于以下原理

两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

先来了解一些数论知识(以下内容摘自《初等数论》,潘承洞著):

####同余

设m不等于0, 若m|a-b,即a-b=km, 则称m为模,a同余于b模m,以及b是a对模m的剩余。记作a≡b(mod m)

####同余类

对给定的模m,有且恰有m个不同的模m的同余类,他们是 0 mod m,1 mod m,…,(m-1)mod m。

####完全剩余系

一组数y1,y2,…,ys称为是模m的完全剩余系,如果对任意的a有且仅有一个yj是a对模m的剩余,即a同余于yj模m。 由此可见0,1,2,…,m-1是一个完全剩余系。因此,如果m个数是两两不同余的,那么这m个数便是完全剩余系。

基于以上知识,我们可以证明这样一个事实,即如果i和n互质的话,那么序列: 0 i mod n 2i mod n 3i mod n …. (n-1)*i mod n 就包括了集合{0,1,2 … n-1}的所有元素。(下一个元素(n)*i mod n 又是0) 为什么呢?

证明: 由于0,1,2,…,n-1本身是一个完全剩余系,即它们两两互不同余。设此序列为Xi(0<=i<=n-1),可得下式: Xi≠Xj (mod n) 注:这里由于不能打出不同余字符因此用不等于替代

由于i与n是互质的,所以 Xii ≠iXj (mod n) 因此i*Xi是m个互不同余数,那么可断定它们是完全剩余系。得证。

有了上面的结论,那么,如果n与k互质,下面的赋值过程就能完成所有值的赋值(设数组为X[0…n-1],长度为n): t = X[0]

X[0] = X[i mod n]

X[i mod n] = X[2i mod n]

……

X[(n-2)i mod n] = X[(n-1)i mod n]

X[(n-1)*i mod n] = t

以上操作已经把包括{0,1,…,n-1}所有元素放到了最终位置上,每次完成一个元素的放置。 根据以上我们得到了一个中间结论,如果n和k互质,我们就可以一次完成所有元素的纺织。那么如果n和k不是互质的呢?

那就是让n和k互质。即让k’=k/gcd(k, n),n’=n/gcd(k,n)。这样就构成了一对互质的数。这就意味着需要把整个数组的每g(g=gcd(k,n))个元素组成块,每个块的k’和n’就互质了。每次相当于把g中的一个元素移到最终的位置,由于g是块元素,每个块含有g个元素,所以总共需要g次移动。

int gcd(int m, int n) {
    if (m % n == 0)
    {
        return n;
    }
    else
    {
        return gcd(n, m%n);
    }
}

void rotate(int nums[], int n, int k)
{
    if (k > n) {
        k %= n;
    }
    if (k % n == 0) return;
    int count = gcd(n, k);
    for(int j = 0; j < count;j++) {
        int temp = nums[n - j - 1];
        int current = n - j - 1;
        int previous = (current - k) % n;
        for (;previous != n - j - 1;previous = (previous - k + n) % n) {
            nums[current] = nums[previous];
            current = previous;
        }
        previous = (previous + k) % n;
        nums[previous] = temp;
    }
}

##解法三 以n-k为界,分别对数组的两边进行逆置,然后再对整个数组进行一次逆置 这个算法的实现原理我能理解,但是为什么要这样做呢?推导过程是从以结果为导向来推导。

以数组arr[5] = {1, 2, 3, 4, 5};为例。

如果n=5,k=2,则旋转结果为{4, 5, 1, 2, 3}

看上去很像整个数组的逆置{5, 4, 3, 2, 1}

但是还需要变换一下才能得到想要的结果:

发现如果将前面(0,k)和后面(k,n)的两部分分别逆置之后就会得到最终的结果。

{5, 4} => {4, 5}

{1, 2, 3} => {3, 2, 1}

于是就有了先将数组前后两部分逆置,然后再将整个数组逆置的解法。

void swap(int arr[], int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void reverse(int arr[], int begin, int end)
{
    int mid = (begin + end) / 2;
    for (int i = begin, j = 0; i < mid; i++, ++j) {
        swap(arr, i, end - j - 1);
    }
}

void rotate(int nums[], int n, int k)
{
    if (k >= n) k %= n;
    reverse(nums, 0, n - k);
    reverse(nums, n - k, n);
    reverse(nums, 0, n);
}

也可以先逆置整个数组,然后在逆置前后两部分。

##解法四 开辟新空间 这个解法就是开辟一个新的空间p保存需要移动的值,然后将原数组移动k位,最后在将p中的值插入到原数组中。

void rotate(int nums[], int n, int k) {
    if (k >= n) {
        k = k % n;
    }

    int *p = new int[k];
    for (int i = 0; i < k; ++i) {
        p[i] = nums[n - k + i];
    }
    for (int j = 0; j < n - k; ++j) {
        nums[n - j - 1] = nums[n - k - j - 1];
    }
    for (int i = 0; i < k; ++i) {
        nums[i] = p[i];
    }
}

记录下自己的分析,如果错误和更多建议,欢迎指出。谢谢阅读。

分享到: 微信 更多