首页 > 试题广场 >

旋转数组

[编程题]旋转数组

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

算法知识视频讲解

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)

Python3

牛客429226965号

class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        # write code here
        if n == 0:
            return a
        # 区间[0, 3)
        def reverse(arr, begin, end):
            left = begin
            right = end - 1
            while left < right:
                arr[left], arr[right] = arr[right], arr[left]
                left += 1
                right -= 1
        # 操作是周期的    
        m = m % n
        # 全部翻转：
        reverse(a, 0, len(a))
        # 翻转前面部分：
        reverse(a, 0, m)
        # 翻转后面的部分：
        reverse(a, m, len(a))
        return a

发表于 2023-08-29 17:12:46 回复(0)

Python3

性感男模小白

class Solution:

def solve(self , n: int, m: int, a: List[int]) -> List[int]:

# write code here

if n>=m:

return a[len(a)-m:]+a[0:len(a)-m]

else:

m%=n

return a[len(a)-m:]+a[0:len(a)-m]

发表于 2023-05-13 13:55:00 回复(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

说这不是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

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)

Python3

牛客116003403号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 旋转数组
# @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]:
        # write code here
        if n==1:
            return a
        if m==0:
            return a
        elif m>n:
            m=m%n
        for i in range(m):
            x =a.pop()
            a.insert(0,x)
        return a

发表于 2023-03-05 23:45:09 回复(0)

Python3

牛客567331391号

class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        list_a = []
        res = []
        if m >= n:
            m = m % n
        for i in range(m):
            list_a.insert(0,a[-1])
            a.pop()

        res = list_a + a
        return res
        # write code here

发表于 2023-02-17 15:42:02 回复(0)

Python3

Jan9360

哈哈，这个最简洁
class Solution:
    def solve(self, n: int, m: int, a: List[int]) -> List[int]:
        # write code here
        m %= n
        return a[-m::] + a[:-m]

发表于 2023-01-26 23:17:45 回复(1)

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)

Python3

JianYue

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 旋转数组
# @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]:
        m = m % n
        if m < n/2:
            for i in range(m):
                x = a.pop()
                a.insert(0, x)
        else:
            for i in range(n-m):
                x = a.pop(0)
                a.append(x)
        return a

发表于 2022-09-21 23:49:25 回复(0)

Python3

E-Doz

class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        # write code here
        a = a[::-1]
        m %= n
        return a[:m][::-1] + a[m:][::-1]

发表于 2022-09-14 23:15:09 回复(0)

Python3

Vivimore

三次反转：第一次将整个数组反转，第二次将前m个元素反转回来，第三次将后面的元素反转回来原来的顺序。

class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        m %= n
        a.reverse()
        a[:m] = a[:m][::-1]
        a[m:] = a[m:][::-1]
        return a

发表于 2022-05-27 19:56:01 回复(0)

Python3

~biubiubiu~

#
# 旋转数组
# @param n int整型数组长度
# @param m int整型右移距离
# @param a int整型一维数组给定数组
# @return int整型一维数组
#
class Solution:
def solve(self , n , m , a ):
# write code here

m = m%n
a.extend(a[0:n-m])
del a[0:n-m]

return a

#但运行时间和占用内存不太行

发表于 2022-01-04 15:50:16 回复(0)

Python3

尹懿汐

#
# 旋转数组
# @param n int整型 数组长度
# @param m int整型 右移距离
# @param a int整型一维数组 给定数组
# @return int整型一维数组
# 整体思想：从a[0]开始右移，目标位置替出来到缓冲区buf。循环数组个数，就能把整个数组右移完。移动数据的次数最大为n。
class Solution:
    def solve(self , n , m , a ):
        if m%n == 0:    # 如果右移距离是长度的倍数，那就直接返回原数组
            return a
        m = m%n    # 右移次数大于数组长度的话当作右移大于数组长度多少来处理。
        index = m    # 初始位置设置在第一个要被换走的数
        buf = a[0]
        if n%m == 0:    # 如果数组长度是右移距离的倍数，那移动倍数此之后，就得换到从a[1]开始移动的地方了。不然会重复移动，是不同轮回的
            time = n/m
            for i in range(n):
                if time==0:
                    buf = a[1]
                    index = (1+m)%n
                    time = n/m
                a[index],buf = buf,a[index]
                index = (index+m)%n
                time -= 1
        else:
            for i in range(n):    # 如果不是整数倍，那一直移动下去都不会重复。
                a[index],buf = buf,a[index]
                index = (index+m)%n
        return a
        # write code here

发表于 2021-08-22 11:19:00 回复(0)