内存移动问题


问题描述

对于有n个元素的数组a[n],将每一位循环向右移动k位。要求算法的空间复杂度不得大于或等于2n。

问题分析

  1. 正常情况下,第i位右移k位后,位置为$(i+k) mod\ n$,但这样移动的话空间复杂度为2n,不符合要求
  2. 也可以一次所有元素后移一位,从后面开始移动,用一个temp变量即可,此时空间复杂度为,虽然符合要求,但是时间复杂度为$O(k\times n)$,比较大
  3. 经实践验证,我们可以移动Q轮,Q为n与k的最大公约数;而每轮移动的元素个数为n/Q个。每轮移动后,最后一个移动的元素会到达最先移动的元素的位置
  4. 每次移动后,第i-1个元素的位置变为$x_i=(x_0+i\times k-n\times (y_0+y_1+\cdots+y_{n-1}))mod\ n$,其中$y_i$为$x_0+k$与n的商,$x_0$为第一个移动的元素。化简后为$x_i=(x_0+i\times k)mod\ n$.
  5. 设第m轮、第i次连续移动后回到初始位置,则必有$x_i=(x_0+i\times k)mod\ n=x_m$
  6. 所以,算法需要两层循环,外层循环为移动的轮数,内层循环为每轮移动的次数,轮数Q为n与k的最大公约数,每轮移动的次数i为n/Q。
  7. 在内层循环中,需要找到本次移动的元素最终要到达的位置
  8. 最后,时间复杂度为$O(n)$,空间复杂度为$O(n+3)=O(n)$

代码

//欧几里得算法求最大公约数
int euclid(int a, int b)
{
    while (b != 0)
    {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

void move(int n, int k, int a[])
{
    int Q = euclid(n, k);
    //外层循环记录轮数,最大为Q轮
    for (int q = 0; q < Q; ++q)
    {
        int temp = a[q];
        int m = q, s;
        //内层循环找到移动元素的最终位置,并放入,将该位置的原元素取出到中间变量
        for (int i = 0; i < n / Q; ++i)
        {
            m = (m + k) % n;
            s = a[m];
            a[m] = temp;
            temp = s;
        }
    }
    printf("After moving: ");
    for (int j = 0; j < n; ++j)
        printf("%d ", a[j]);
}

int main()
{
    int n, k;
    printf("Input the number of the array: ");
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; ++i)
        a[i] = i;
    printf("Input k: ");
    scanf("%d", &k);
    move(n, k, a);

    return 0;
}

改进算法

从后往前,倒推。

void move(int n, int k, int a[])
{
    int Q = euclid(n, k);
    for (int q = 0; q < Q; ++q)
    {
        int i = n / Q - 1, m = q, p1 = (m + i * k) % n, temp = a[p1];
        for (i = i - 1; i >= 0; --i)
        {
            int p2 = (m + i * k) % n;
            a[p1] = a[p2];
            p1 = p2;
            a[p2] = temp;
        }
    }
    printf("After moving: ");
    for (int j = 0; j < n; ++j)
        printf("%d ", a[j]);
}

文章作者: 恰醋
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 恰醋 !
评论
 上一篇
下一篇 
穿越沙漠问题求解 穿越沙漠问题求解
问题描述一辆吉普车来到1000km宽的沙漠边沿。吉普车的耗油量为1L/km,最大装油量为500L。显然,吉普车必须用自身油箱中的油在沙漠中设几个临时加油点,否则是通不过沙漠的。假设在沙漠边沿有充足的汽油可供使用,那么吉普车应在哪些地方、建多
2020-04-13
  目录