在python中旋转列表最有效的方法是什么? 现在我有这样的东西:

>>> def rotate(l, n):
...     return l[n:] + l[:n]
... 
>>> l = [1,2,3,4]
>>> rotate(l,1)
[2, 3, 4, 1]
>>> rotate(l,2)
[3, 4, 1, 2]
>>> rotate(l,0)
[1, 2, 3, 4]
>>> rotate(l,-1)
[4, 1, 2, 3]

有没有更好的办法?


当前回答

下面是一个高效的算法,不需要使用任何额外的数据结构:

旋转(nums: List[int], k: int):

    k = k%len(nums)
    l, r = 0, len(nums)-1
    while (l<r):
        nums[l], nums[r]= nums[r], nums[l]
        l,r=l+1,r-1
    
    l,r = 0, k-1
    while (l<r):
        nums[l], nums[r]=nums[r], nums[l]
        l,r=l+1,r-1
        
    l,r=k,len(nums)-1
    while (l<r):
        nums[l], nums[r]=nums[r], nums[l]
        l,r=l+1,r-1

其他回答

可能更适合使用ringbuffer。它不是一个列表,尽管出于您的目的,它的行为可能足够像一个列表。

问题是列表上移位的效率是O(n),这对于足够大的列表来说非常重要。

在环缓冲区中移动只是更新了头的位置也就是O(1)

deque对两端的拉和推进行了优化。它们甚至有一个专用的rotate()方法。

from collections import deque
items = deque([1, 2])
items.append(3)        # deque == [1, 2, 3]
items.rotate(1)        # The deque is now: [3, 1, 2]
items.rotate(-1)       # Returns deque to original state: [1, 2, 3]
item = items.popleft() # deque == [2, 3]

Numpy可以使用roll命令做到这一点:

>>> import numpy
>>> a=numpy.arange(1,10) #Generate some data
>>> numpy.roll(a,1)
array([9, 1, 2, 3, 4, 5, 6, 7, 8])
>>> numpy.roll(a,-1)
array([2, 3, 4, 5, 6, 7, 8, 9, 1])
>>> numpy.roll(a,5)
array([5, 6, 7, 8, 9, 1, 2, 3, 4])
>>> numpy.roll(a,9)
array([1, 2, 3, 4, 5, 6, 7, 8, 9])

我能想到的最简单的方法:

a.append(a.pop(0))

如果只使用pop(0)呢?

list.pop([我]) 删除列表中给定位置的项,并返回它。如果 如果没有指定索引,a.pop()将删除并返回中的最后一项 列表中。(方法签名中i周围的方括号 表示参数是可选的,而不是您应该键入square 括号在那个位置。你会经常在 Python库参考。)