首页 > 试题广场 >

旋转数组

[编程题]旋转数组

热度指数：62995 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，即将A中的数据由（A₀ A₁ ……A_N-1 ）变换为（A_N-M …… A_N-1 A₀ A₁ ……A_N-M-1 ）（最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

数据范围： $0 < n \le 100$ ， $0 \le m \le 1000$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

6,2,[1,2,3,4,5,6]

输出

[5,6,1,2,3,4]

示例2

输入

4,0,[1,2,3,4]

输出

[1,2,3,4]

备注:

(1<=N<=100,M>=0)

算法知识视频讲解

牛客44818152号

int* solve(int n, int m, int* a, int aLen, int* returnSize ) {
    // write code here
    * returnSize=aLen;
    int i = 0;
    while(m--)
    {
        int t = a[n-1];
        for(i=n-2;i>=0;i--)
        {
            a[i+1]=a[i];
        }
        a[0]=t;
    }
    return a;
}

发表于 2024-09-13 21:10:58 回复(0)

crease_yii

核心：注意取模

发表于 2024-03-26 11:14:32 回复(0)

一个优雅的程序猿

void reverse(int* a, int aLen) {

int i,t;

for(i=0;i<aLen/2;i++) {

t = a[i];

a[i] = a[aLen-i-1];

a[aLen-i-1] = t;

}

int* solve(int n, int m, int* a, int aLen, int* returnSize ) {

reverse(a,aLen);

reverse(a,m%n);

reverse(a+m%n,n-m%n);

*returnSize = aLen;

return a;

}

编辑于 2024-03-13 14:45:22 回复(0)

脉冲星

int* solve(int n, int m, int* a, int aLen, int* returnSize ) {
    // write code here
    //比较笨的办法是 依次旋转
    int step = m % n;
    int buf;
    while(step--) {
        buf = a[aLen-1];
        for (int i=aLen-1;i>0;i--) {
            a[i] = a[i-1];
        }
        a[0] = buf;
    }
    *returnSize = aLen;
    return a;
}

发表于 2023-02-18 13:03:58 回复(1)

_Herc

C语言

int* solve(int n, int m, int* a, int aLen, int* returnSize ) {
    // write code here
    m = m%n;
    *returnSize = aLen;
    int last,temp;
    for(int i=0; i<m; i++){
        {
            last=a[aLen-1];             //先保存最后一个元素
            for(int j=aLen-1; j>0; j--){    //从倒数第二个开始，依次把元素赋给下一个，相等于除了最后一个元素，整体右移
                a[j] = a[j-1];
            }
            a[0] = last;                //将原数组最后一个元素赋值给首位
        }
    }
    return a;
}

发表于 2022-11-20 09:55:45 回复(0)

牛客40918255号

很想吐槽一下： int* returnSize这个完全就没有啥用处，拿来作为返回数组行数使用，明明n都作为传入了，再传出来的意义在哪呢？

int* solve(int n, int m, int* a, int aLen, int* returnSize ) {
    // write code here
    int *p=(int*)malloc(sizeof(int)*n);
    int *temp=(int*)malloc(sizeof(int)*n);
    int i=0,j=0;
    *returnSize=n;
    if(m>n){
        m=m%n;
    }
    for(i=0;i<m;i++){
        temp[i]=a[n-m+i];
    }
     for(j=0;j<n-m;j++){
        p[j+m]=a[j];
    }
    for(j=0;j<m;j++){
        p[j]=temp[j];
    }
    
    return p;
}

发表于 2021-08-07 00:07:47 回复(0)