首页 > 试题广场 >

旋转数组

[编程题]旋转数组

热度指数：53172 时间限制：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)

算法知识视频讲解

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

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)

C/C++

两份鸡柳送到九楼

注意取模

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 || a.empty()) return {};
if (!m) return a;
m %= n; // 注意取模
reverse(a.begin(), a.end());
reverse(a.begin(), a.begin() + m);
reverse(a.begin() + m, a.end());
return a;
}
};

发表于 2020-10-10 15:46:38 回复(0)

Java

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)

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)

JavaScript

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)

C++

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)

Java

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)

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++

神秘巨星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号

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)

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 回复(3)

C++

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

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

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)

Python3

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)

JavaScript Node

Whiskeyi

function solve( n ,  m ,  a ) {
   for (let i = 0; i < m; i++) {
       a.unshift(a.pop())
   }
   return a
}

发表于 2022-11-06 20:55:46 回复(1)

C++

Spectre_

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) {
        // 时间复杂度O(N)，空间复杂度O(1)
         m %= n;
         reverse(a, 0, n - 1);
         reverse(a, 0, m - 1);
         reverse(a, m, n - 1);
         return a;
    }
    void reverse(vector<int> &a, int left, int right) {
        while (left < right) {
            a[left] = a[left] ^ a[right];
            a[right] = a[left] ^ a[right];
            a[left] = a[left] ^ a[right];
            ++left; --right;
        }
    }
};

发表于 2022-10-21 15:28:29 回复(0)