时间戳

首页 > 解决方案 > 列表弹出和插入在python中非常慢

python - 列表弹出和插入在python中非常慢

问题描述

我正在处理一个 leetcode 问题 189. Rotate Array。

问题陈述：给定一个数组，将数组向右旋转 k 步，其中 k 是非负数。输入：nums = [1,2,3,4,5,6,7], k = 3 输出：[5,6,7,1,2,3,4]

以下是我的代码。我的理解是时间复杂度是 O(k)，但它最终非常低。您能否对此有所了解并教育我？

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        while k:
            nums.insert(0,nums.pop())
            k -= 1

标签： pythonlist

解决方案

一种方法是使用 deque rotate，如下所示

from collections import deque
from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        dnums = deque(nums)
        dnums.rotate(k)
        nums[:] = dnums


nums = [1,2,3,4,5,6,7]
Solution().rotate(nums, 3)
print(nums)

输出

[5, 6, 7, 1, 2, 3, 4]

从文档（强调我的）：

向右旋转双端队列 n 步。如果 n 为负数，则向左旋转。当 deque 不为空时，向右旋转一步相当于d.appendleft(d.pop())，向左旋转一步相当于 d.append(d.popleft())。

在列表开头插入的问题是它是 O(n)，您必须移动所有元素。在开头插入的双端队列（appendleft）是 O(1)。

有关 deque 和 list 的时间复杂度的更多详细信息，请参阅here

推荐阅读