首页 > 试题广场 >

旋转数组

[编程题]旋转数组
  • 热度指数：65287 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …… AN-1 A0 A1 ……AN-M-1 ）（最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

数据范围：，
进阶：空间复杂度 ，时间复杂度
示例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)
算法知识视频讲解
添加回答
Java
matrixZ头像 matrixZ
三次翻转
假设 n=7且 k=3
原始数组                  : 1 2 3 4 5 6 7
反转所有数字后             : 7 6 5 4 3 2 1
反转前 k 个数字后          : 5 6 7    4 3 2 1
反转后 n-k 个数字后        : 5 6 7    1 2 3 4 --> 结果 
import java.util.*;
public class Solution {
    public int[] solve (int n, int m, int[] a) {
        int k=m%n;
        reverse(a,0,n-1);
        reverse(a,0,k-1);
        reverse(a,k,n-1);
        return a;
    }
    
    public void reverse(int[] a,int start,int end){
        while (start<end){
            int temp=a[start];
            a[start]=a[end];
            a[end]=temp;
            start++;
            end--;
        }
    }
}



发表于 2020-11-14 18:02:45 回复(14)
JavaScript
JZZZZZZZZZZZ头像 JZZZZZZZZZZZ
把头部移动到尾部，计算好移动次数即可function solve( n ,  m ,  a ) { 
    // write code here
    
    for(let i=0;i<n-m%n;++i){
        a.push(a.shift())
    }
    return a
    
}


编辑于 2021-03-10 08:57:52 回复(1)
Java
肥猿头像 肥猿
先把0~(n-m)处的数组翻转，再把(n-m)~n处的数组翻转，最后把整个数组翻转，整个时间复杂度为O（n），空间复杂度为O(1) 
import java.util.*;
public class Solution {
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型一维数组 给定数组
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] a) {
        // write code here
        m=m%n;
        m=n-m;
        for(int i=0;i<m/2;i++){
            int temp=a[i];
            a[i]=a[m-1-i];
            a[m-1-i]=temp;
        }
        for(int i=m;i<(a.length+m)/2;i++){
            int temp=a[i];
            a[i]=a[a.length-1+m-i];
            a[a.length-1+m-i]=temp;
        }
        for(int i=0;i<a.length/2;i++){
            int temp=a[i];
            a[i]=a[a.length-1-i];
            a[a.length-1-i]=temp;
        }
        return a;
    }
}


发表于 2021-03-18 09:44:44 回复(0)
Java
试看天地翻覆头像 试看天地翻覆
按m值分批次翻转
此方法比三次翻转的交换次数更少
输入： 
6,2,[1,2,3,4,5,6]
三次翻转：
反转所有数字        6 5 4 3 2 1   交换3次
反转前m个数         5 6 4 3 2 1    交换1次
反转后n-m个数      5 6 1 2 3 4    交换2次
共交换6次；

分批翻转：
第1批1次：        3 2 1 4 5 6    交换1次
第1批2次：        5 2 1 4 3 6    交换1次
第2批1次：        5 4 1 2 3 6    交换1次
第2批2次：        5 6 1 2 3 4    交换1次
共交换4次；
import java.util.*;
public class Solution {
    public int[] solve (int n, int m, int[] a) {
        m = m % n;
        for (int i = 0; i < m; i++)
            for (int j = i + m; j % n != i; j++) {//一次交换后，元素便放置到了正确位置
                int tmp = a[i];
                a[i] = a[j % n];
                a[j % n] = tmp;
            }
        return a;
    }
}


发表于 2022-03-22 14:53:48 回复(2)
C++
reddream007头像 reddream007 
class Solution {
public:
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型vector 给定数组
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a) {
        // write code here
            int z = m  % n;
            reverse(a.begin(),a.end());
            reverse(a.begin(),a.begin()+z);
            reverse(a.begin()+z,a.end());
            return a;
       
      
    }
};

发表于 2021-10-12 16:32:36 回复(0)
Python3
Osusapi头像 Osusapi

投机取巧不可取

class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        # write code here
        return list(a[-(m%n):])+list(a[:-(m%n)])
发表于 2023-03-28 15:00:54 回复(0)
Java
yxjing头像 yxjing 
import java.util.*;


public class Solution {
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型一维数组 给定数组
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] a) {
        // write code here
        int temp=0;
        for(int t=1;t<=m;t++){
            temp=a[n-1];
            for(int i=n-2;i>=0;i--){
                a[i+1]=a[i];
            }
            a[0]=temp;
        }
        return a;
    }
}

发表于 2022-08-25 15:25:29 回复(1)
C++
神秘巨星1头像 神秘巨星1
数组往右移动m mod n次，时间复杂度：O(mn)，空间复杂度：O(1) 
class Solution {
public:
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型vector 给定数组
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a) {
        // write code here
        int r = m % n;
        if (r == 0) return a;
        
        while (r > 0) {
            int temp = a[n-1];
            for (int i = n - 1; i > 0; --i) {
                a[i] = a[i - 1];
            }
            a[0] = temp;
            --r;
        }
        
        return a;
    }
};


发表于 2022-02-27 15:48:19 回复(0)
C++
牛客559267693号头像 牛客559267693号
vector<int> solve(int n, int m, vector<int>& a) {
        // write code here
        m=m%n;
        reverse(a.begin(),a.end());
        reverse(a.begin(), a.begin()+m);
        reverse(a.begin()+m,a.end());
            return a;
    }
发表于 2021-08-16 10:36:44 回复(0)
Java
惠灵顿靖头像 惠灵顿靖 
import java.util.*;


public class Solution {
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型一维数组 给定数组
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] a) {
        // write code here
        int mm=m%n;
        for (int count=0;count<mm;count++){
//          这个方法是自己想的，起初打算用一个变量暂存，然后依次往后存数，
//          发现一个变量不够用，于是想到可以用两个变量交替存，
//          但是交替带来了奇偶的问题。最后需要注意i+1带来边界溢出的问题，故需要取余
            int t1=a[0],t2=a[1];
            for (int i=0;i<n;i++){
                if(i%2==0){
                    t2=a[(i+1)%(n)];
                    a[(i+1)%(n)]=t1;  
                }
                if(i%2==1){
                    t1=a[(i+1)%(n)];
                    a[(i+1)%(n)]=t2;
                    
                }
            }
        }
        return a;
    }
}

发表于 2021-07-15 23:19:39 回复(0)
WYACAC头像 WYACAC 
import java.util.*;


public class Solution {
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型一维数组 给定数组
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] a) {
        // write code here
        m = m%n;
        reverse(a,0,n-m-1);
        reverse(a,n-m,n-1);
        reverse(a,0,n-1);
        return a;
    }
    public void reverse(int[] a,int start,int end){
        int i = start;
        int j = end;
        while(i<j){
            int tem = a[i];
            a[i] = a[j];
            a[j] = tem;
            i++;
            j--;
        }
    }
}

发表于 2021-03-23 10:59:30 回复(0)
Stackingrule头像 Stackingrule 
class Solution {
public:
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型vector 给定数组
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a) {
        // write code here
        if (n == 0 || (m %= n) == 0) return a;
        reverse(a.begin(), a.begin() + n - m);
        reverse(a.begin() + n - m, a.end());
        reverse(a.begin(), a.end());
        return a;
    }
};
发表于 2020-08-18 22:33:37 回复(4)
Java
黄梅花头像 黄梅花
1.首先要找出要有效移动的总步骤，m%n，求余就是移动步骤

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 旋转数组
* @param n int整型 数组长度
* @param m int整型 右移距离
* @param a int整型一维数组 给定数组
* @return int整型一维数组
*/
public int[] solve (int n, int m, int[] a) {
// write code here
if(m==0){
return a;
}
int movestep = m % n;
for(int i=0;i<movestep;i++){
int before = a[n-1];
for(int j=n-1;j>0;j--){
a[j] = a[j-1];
}
a[0] = before;
}
return a;
}
}

发表于 2025-02-27 23:39:23 回复(0)
Python3
勇敢小小小牛头像 勇敢小小小牛 
class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        # write code here
        m = m % n
        return a[-m:]+a[:-m]
编辑于 2024-03-18 18:46:39 回复(0)
C++
FLYFREELY头像 FLYFREELY
数组置换（不使用reverse操作） 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型vector 给定数组
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a) {
        // write code here
        //n表示数组中的整数个数，m表示右移个数，可以遍历输出
        //为了保留原始顺序，动态数组b作为a的拷贝
        vector<int> b = a;
        if (m > n) m = m % n;
        for(int i = 0; i < m; i++) {
            a[i] = a[n - m + i];
        }
        for (int j = m; j < n; j++) {
            a[j] = b[j - m];
        }
        return a;
    }
};


发表于 2023-08-13 16:48:24 回复(0)
MoodD头像 MoodD 
class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& a) {
        // write code here
        m = m % a.size();
        while(m)
        {
            int temp = a[n - 1];
            for(int i = n; i >= 2; i--)
            {
                a[i - 1] = a[i - 2];
            }
            a[0] = temp;
            m--;
        }
        return a;
    }
};

发表于 2023-07-20 11:44:07 回复(0)
Python3
说这不是bug的大魔王很忧伤头像 说这不是bug的大魔王很忧伤 
class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        # write code here
        for i in range(m):
            a.insert(0,a[-1])
            a.pop()
        
        return a
我觉得这样写也挺简单的啊
发表于 2023-03-24 15:43:50 回复(1)
Python3
Giho头像 Giho
class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        m = m % n
        return a[n-m:] + a[:n-m]

发表于 2023-03-12 18:13:19 回复(1)
华夫饼躺平又起来了头像 华夫饼躺平又起来了 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 旋转数组
# @param n int整型 数组长度
# @param m int整型 右移距离
# @param a int整型一维数组 给定数组
# @return int整型一维数组
#
class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        if m == 0:
            return a
        loc = n - m % n
        return a[loc:] + a[:loc]

发表于 2023-02-24 18:05:38 回复(0)
Python3
马各头像 马各
所以为啥要翻转，直接切片不香吗 
class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        # write code here
        m=m%n
        if m==0:
            return a
        return a[n-m:]+a[:n-m]
发表于 2022-11-09 01:03:11 回复(0)
提交观点

问题信息

数组
上传者：牛客332641号
难度：
172条回答 7203浏览

热门推荐

通过挑战的用户

查看代码

相关试题

旋转数组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号