在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]
有没有更好的办法?
在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]
有没有更好的办法?
当前回答
我能想到的最简单的方法:
a.append(a.pop(0))
其他回答
下面是一个高效的算法,不需要使用任何额外的数据结构:
旋转(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
这取决于你这样做的时候想要发生什么:
>>> shift([1,2,3], 14)
你可能想要改变你的:
def shift(seq, n):
return seq[n:]+seq[:n]
to:
def shift(seq, n):
n = n % len(seq)
return seq[n:] + seq[:n]
可能更适合使用ringbuffer。它不是一个列表,尽管出于您的目的,它的行为可能足够像一个列表。
问题是列表上移位的效率是O(n),这对于足够大的列表来说非常重要。
在环缓冲区中移动只是更新了头的位置也就是O(1)
下面的方法是O(n)到位,辅助内存不变:
def rotate(arr, shift):
pivot = shift % len(arr)
dst = 0
src = pivot
while (dst != src):
arr[dst], arr[src] = arr[src], arr[dst]
dst += 1
src += 1
if src == len(arr):
src = pivot
elif dst == pivot:
pivot = src
请注意,在python中,这种方法与其他方法相比效率非常低,因为它不能利用任何部分的本机实现。
如果效率是你的目标,(周期?内存?),您最好查看数组模块:http://docs.python.org/library/array.html
数组没有列表的开销。
就纯粹的列表而言,你所拥有的就是你所希望做的。