谁能指导我使用 O(1) 时间复杂度来旋转数组的替代解决方案

Question

for i in range(D):
   ele=A.pop(0)
   ans=A.append(ele)
   return ans

上面的代码是我写的，其中d是数组逆时针旋转的次数，A是数组。

Answer 1

您的代码已经运行在 O(1) 中，就像您 return 一次迭代后一样。如果我们解决这个问题，我们会得到这样的东西：

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

但它 return 是 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，数组的通常定义也会给您一个线性下限。如果数组定义为从给定地址开始，那么每个元素在内存中都是连续的，你不能在不移动元素的情况下重新排列元素，并且旋转必须移动它们的 all，因此你不能比 Θ(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) space——即进行旋转 in-place，修改 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) space 中轻松完成——和旋转：

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

当你先反转前缀 in-place 然后反转后缀时，你会得到 rev(x[:offset])+rev(x[offset:]) 并且当你反转整个序列时前缀变成后缀，反之亦然，并且反转撤销原始一，所以你剩下 x[offset:]+x[:offset] 这是旋转。

谁能指导我使用 O(1) 时间复杂度来旋转数组的替代解决方案

Can anyone guide me the alternative solution that takes O(1) time complexity for the rotation of the array

list

data-structures