时间戳

首页 > 解决方案 > Python3 循环：超出时间限制，代码优化

python-3.x - Python3 循环：超出时间限制，代码优化

问题描述

我正在尝试通过在 HackerRank.com 上解决简单的数据结构问题来学习 python。我试图解决左旋转挑战：

对大小数组的左旋转操作将数组的每个元素向左移动1 个单位。给定一个整数，, 旋转剩余多步的数组并返回结果。

例子

= 2
= [1, 2, 3, 4, 5] 2 次旋转
后， = [3, 4, 5, 1, 2]。

我建议了以下解决方案。它适用于 8 个用例，但在最后两个用例中出现超时错误。

def rotateLeft(d, arr):
    new = arr[0:]
    for _ in range(d):
        i, new = new[0], new[1:]
        new.append(i)
    return new

我不是在寻找一些基于公式的单线解决方案。我知道它会解决手头的问题，但它不会帮助我理解如何优化基于循环的简单解决方案。

我正在寻找优化规则，对于这个问题和一般来说。

标签： python-3.xloopsoptimization

解决方案

当您意识到d可能比列表的大小大很多倍时，优化是可能的。在这种情况下，您将浪费时间轮换列表，只是将其多次恢复到原始顺序以最终达到预期的轮换。

所以只进行d % len(arr)旋转。

第二个优化是您实际上不必逐个执行旋转。您可以d % len(arr)通过从左侧切出许多值（在一次操作中）并将它们附加到右侧（在一次操作中）来一次性完成旋转。这样，您的代码甚至不会有显式循环。

所以在 Python 中这很容易：

def rotateLeft(d, arr):
d %= len(arr)
return arr[d:] + arr[:d]

如果您想通过一次移动一个值来执行此操作，而不进行切片或列表理解，请执行以下操作：

def rotateLeft(d, arr):
    result = []
    for i in range(len(arr)):
        result.append(arr[(i + d) % len(arr)])
    return result

...但这不是那么有效。切片是 Pythonic 的方式。

推荐阅读