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)) может быть упрощена, но я считаю, что это не проблема, вызывающая чрезмерное время выполнения.

Вам следует избегать просмотра списка с самого начала на каждой итерации. Когда вы найдете свой первый «несортированный» индекс, вы должны следить за ним, чтобы при следующем проходе вы начинали процесс оттуда, а не каждый раз с нуля индекса. Это должно сократить ненужные циклы по мере постепенной сортировки массива.

Во-вторых, в заявлении о проблеме не требуется увеличивать порядок индексов, поэтому вы можете выбрать любые 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]