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

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]

问题是在 10 个测试用例中的 2 个中，hackerrank 将我的代码计算在内

我读到使用带有 range() 函数的 for 循环比在 python 中使用 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

您在不必要的情况下使用for循环d会使解决方案的时间复杂度为O(nxd)，其中n的长度是a. 您可以直接将列表切片d，并且考虑到d大于或等于 的长度的情况a，您可以使用 的d长度上的余数a，这样解决方案的时间复杂度只需O(n)：def rotLeft(a, d):    offset = d % len(a)    return a[offset:] + a[:offset]

Answer 2

想想看，如果你需要移位["a","b","c","d"]100001 次……结果是什么？与移动它 1 次相同。为什么？因为 100000 可以被 4 整除（您的列表的长度） - 在 4 次移动之后，您的列表恢复到原来的状态 - 所以如果完全移动 25k 次，您可以再次移动 - 或者简单地计算“无意义”的移动并移动一次.比在循环内执行轮班要快得多。