Python时间复杂性

Question

这个节目是为了比赛。但它超过了时间。那么，有什么方法可以让代码运行得更快呢。如果您能建议如何用python高效地打印二维列表。我想打印二维列表中的int。 详细程序说明的链接：https://www.codechef.com/MAY20B/problems/TRPLSRT

  for i in range(int(input())):
   N,K = map(int,input().split())
   arr=list(map(int,input().split()))
   shift = []
   shiftList = []
   temp = 0
   c = 0
   while(c < K):
      c += 1
      for i in range(len(arr)):
         if(arr[i] != (i+1) ):
            shift.append(i)
            if(len(shift)==3):
               shiftList.append(shift)
               temp = arr[shift[-1]]
               arr[shift[-1]] = arr[shift[-2]]
               arr[shift[-2]] = arr[shift[-3]]
               arr[shift[-3]] = temp
               shift = []
               break

   if(arr == sorted(arr)):   
      print(len(shiftList))
      for i in range(len(shiftList)):
         for j in range(len(shiftList[i])):
            print(shiftList[i][j] + 1,end=" ")
         print()   
   else:
      print(-1)

Answer 1

代码的for i in range(len(arr))部分可以简化，但我相信这不是导致运行时间过长的问题

您应该避免在每次迭代时从一开始就查看列表。当您找到第一个“未排序”索引时，您应该跟踪它，以便在下一次传递时，您可以从那里开始该过程，而不是每次都从索引0开始。当您逐步对数组排序时，这将减少不必要的循环

其次，问题陈述不要求索引按递增顺序排列，因此您可以选择列表中的任意3个索引。最佳策略是选择3个指数，以便换档操作在其适当位置放置至少两个值：

• i1应该是第一个未排序的位置
• i2应该是i1的适当值所在的索引。它将位于一个索引>；i1，因为i1是第一个未排序的位置
• i3应该是i2的适当值所在的索引。这一个有点棘手，因为当您达到i2所需的索引时，您可能已经通过了该位置。因此有两种可能性：
• a） i2的值比i2远：只要找到它就使用它
• b） i2的值在i2之前：使用在i1和i2之间找到的上一个索引，并在下一次传递时自行解析

def shift3(K,p):
    lasti = 0
    for _ in range(K):
         i1 = i2 = i3 = None
         for i in range(lasti,len(p)):
             print(i,i1,i2,i3)
             if p[i] == i+1:                       # find next unsorted position
                continue
             if i1 is None:                        # use first unsorted position as i1
                lasti = i1 = i                     # also record highest sorted position
                continue
             if p[i] == i1+1:                      # i2 is position of element that should be at i1
                 i2 = i
             if i3 is None or p[i] == i2+1:        # i3 is position of i2 element (if possible)
                 i3 = i
             if i2 is not None and i3 is not None: # perform shift
                 p[i1],p[i2],p[i3] = p[i2],p[i3],p[i1]
                 break

x = [1,7,3,2,4,6,5]
shift3(5,x)
print(x)
# [1, 2, 3, 4, 5, 6, 7]