for i in range(D):
ele=A.pop(0)
ans=A.append(ele)
return ans
上面的代码是我写的，其中d是数组逆时针旋转的次数，A是数组。
当您在一次迭代后返回时，您的代码已经在O(1)中运行。如果我们修复了这个问题，我们将得到这样的内容:
def rot(x: list[T], offset: int) -> list[T]:
"""Rotates x by offset."""
ans: list[T] = []
for _ in range(offset):
ans.append(x.pop(0))
return ans
，但它返回x的前缀，而不是旋转。它只是将元素复制到ans中。
如果你附加到x，而不是一个新的列表ans，你将得到你的旋转。
def rot(x: list[T], offset: int) -> list[T]:
"""Rotates x by offset."""
for _ in range(offset):
x.append(x.pop(0))
return x
它不能在O(n)中运行——远非如此。
x.pop(0)操作本身在O(n)中运行，因为它涉及到将x中的所有剩余元素向前复制一次，所以如果我们执行offset次，则运行时间为O(offset * n)。
我们能做得更好吗?当然可以。旋转x无非是x[:offset] + x[:offset](或者类似的，如果你允许负偏移)，所以这个函数旋转x
def rot(x: list[T], offset: int) -> list[T]:
"""Rotates x by offset."""
return x[offset:] + x[:offset]
，它在O(n)中这样做，因为我们只复制x的每个元素一次(或至少一个常数次)。它还有一个额外的好处，那就是不会破坏原来的x，但这是否重要取决于旋转的应用，并不总是重要的。
无论如何，如果你想让x保持不变而不修改它，你通常必须在修改一个新数组之前复制它的所有元素，这就给Ω(n)的速度设置了一个下限。
即使你不修改x，数组的通常定义也会给你一个线性下界。如果数组被定义为从给定地址开始，那么在内存中每个元素都是连续的，你不能在不移动元素的情况下重新排列元素，并且旋转必须移动所有元素，因此你不能比Θ(n)做得更好。
但这并不意味着我们不能得到恒定的时间旋转。它只是意味着我们不能用的方式得到它。我们可以改变数组的含义。
例如，我们可以在对象中封装一个底层的(真实的)数组，即连续的项序列，它也记住我们旋转了多少的偏移量。当我们索引它时，我们调整偏移量——i -> (i+offset)%n——这看起来就像我们旋转了数组。
@dataclass
class Array(Generic[T]):
"""Array with constant time rotations."""
arr: list[T] # Underlying data
offset: int = 0 # Current offset
def rot(self, offset: int) -> Array[T]:
"""Rotates self by offset."""
return Array(self.arr, self.offset + offset)
def __getitem__(self, i: int) -> T:
"""Get the value at index i."""
return self.arr[(i + self.offset) % len(self.arr)]
def __str__(self) -> str:
"""Printing string."""
items = ', '.join(str(self[i]) for i, _ in enumerate(self.arr))
return f"[{items}]"
如果我们旋转一个数组，它很好地模拟了旋转，但我们只做了恒定的功。
>>> x = Array([1, 2, 3, 4, 5, 6, 7, 8])
>>> print(x.rot(2))
[3, 4, 5, 6, 7, 8, 1, 2]
在这里，您也可以对相同的底层数组使用不同的旋转方式进行多个引用。如果你修改了数组，那么所有的引用都会看到这个变化——如果你想要比O(n)旋转得更快，你就不能跳出来。
x[:offset] + x[offset:]旋转使用O(n)内存。是的，我们已经为x使用了O(n)内存，但有时我们不使用比我们已经做的更多的内存很重要，所以另一个有趣的问题是，如果我们可以在O(1)空间中旋转——即。在不使用额外内存的情况下修改x。
假的Array旋转当然可以做到这一点，但我们能做到这一点吗?
简单旋转
def rot(x: list[T], offset: int) -> list[T]:
"""Rotate x by offset."""
for _ in range(offset):
x.append(x.pop(0))
return x
这样做，但代价是O(offset * n)的时间。我们可以在O(n)中做到吗?
是的，因为在反转序列(我们可以很容易地在O(n)时间和O(1)空间中做到)和旋转之间存在很好的关系:
def rev(x: list[T], i: int, j: int) -> None:
"""Reverse x[i:j] in-place."""
j -= 1 # first element actually in the range
while i < j:
x[i], x[j] = x[j], x[i]
i += 1
j -= 1
def rot(x: list[T], offset: int) -> list[T]:
"""Rotate x by offset."""
rev(x, 0, offset)
rev(x, offset, 0)
rev(x, 0, len(x))
return x
当你先反转前缀，然后是后缀，你得到rev(x[:offset])+rev(x[offset:])，当你反转整个序列时，前缀变成后缀，反之亦然，这种反转撤销了原来的，所以你剩下的是x[offset:]+x[:offset]，这是旋转。