我应该如何优化和处理我在左旋转问题中遇到的超时错误?

Question

我在hackrrank上为左 https://www.hackerrank.com/challenges/array-left-rotation/problem?isFullScreen=true 旋转问题编写了代码。它在某些测试用例中工作正常，但对于具有较高值的测试用例，它显示超时错误。

由于超时:(而终止

我应该如何优化？

我尝试每次将值存储在数组中，然后再次调用该数组以进行旋转操作。这是需要时间的地方吗？

n = 5
d = 4
a = [1,2,3,4,5]
arr_list_traversals = []
count = 0
while d > 0:
arr = []
for index in range(len(a)):
arr.append(0)
for i in range(0, len(a)):
if i == 0:
arr[len(a)-1] = a[0]
else:
arr[i-1] = a[i]
arr_list_traversals.append(arr)
count += 1
a = arr_list_traversals[count-1]
d -= 1
print(arr)

我知道SO上有很多相关帖子，但我想知道我的代码出了什么问题以及如何让它工作？

对不起，如果这似乎重复。

Answer 1

因为你的移位数组一次一个，你的解决方案是O(n*d(，因为d<=n，它基本上是O(n^2(。你可以将数组移位一次，从而拥有 O(n( 算法。你这样切割阵列。

left = a[d:]
right = a[:d]
for item in left+right:
print(item, end=' ')

编辑： 如果更难理解数组切片，这与使用 for 循环相同。

result = []
for i in range(d,len(a)):
result.append(a[i])
for i in range(d):
result.append(a[i])   
for item in result:
print(item, end=' ')

注意：因为运行 d 次的 while 循环被移除，现在时间复杂度从 O(N*D( 降低到 O(N(