python - 为什么我的切换数组元素的代码不够快？

Question

我应该编写一段代码，将数组的每个元素向左移动一个位置，并执行此操作 d 次。 例如: 如果数组为 [1,2,3,4,5] 并且 d 的值为 2，则应输出以下内容:[3,4,5,1,2](它随着每次迭代而变化，如下所示:[1, 2,3,4,5]==>[2,3,4,5,1]==>[3,4,5,1,2]

问题是 hackerrank 在 10 个测试用例中的 2 个中对我的代码进行了计算

我读到，在 python 中使用 for 循环和 range() 函数比使用 while 循环要快得多。所以我消除了所有 while 循环并使代码尽可能简洁。但是，当数组中数字的大小和数量太大时，代码仍然会超时。

这是我的代码(因大数字而失败):

def rotLeft(a, d):
    for i in range(0,d):
        a=a[1:]+a[:1]
    return a

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nd = input().split()

    n = int(nd[0])

    d = int(nd[1])

    a = list(map(int, input().rstrip().split()))

    result = rotLeft(a, d)

    fptr.write(' '.join(map(str, result)))
    fptr.write('\n')

    fptr.close()

这段代码是我在 hackerrank 上找到的一个解决方案(虽然我认为它是针对 python 2 的，但这并不重要):

def array_left_rotation(a, n, k):
    return a[k:] + a[:k]


n, k = map(int, raw_input().strip().split(' '))
a = map(int, raw_input().strip().split(' '))
answer = array_left_rotation(a, n, k);
print ' '.join(map(str,answer))

解决方案代码通过所有测试输入，但当数字变得太大太多时，我的代码会失败。

Answer 1

您在 d 上使用 for 循环不必要地使解决方案的时间复杂度为 O(n x d)，其中 n 是a 的长度。您可以直接在 d 处对列表进行切片，并且考虑到 d 大于或等于 a 长度的情况，您可以在 a 的长度上使用 d 的余数，因此该解决方案的时间复杂度仅为 O(n):

def rotLeft(a, d):
    offset = d % len(a)
    return a[offset:] + a[:offset]