Уменьшить элементы массива - PullRequest
Новая
       7

Уменьшить элементы массива

0 голосов
/ 12 мая 2019

Учитывая массив или список чисел
например,
[1, 4, 6, 7, 9, 10, 11, 12, 13, 15]

Мы должны уменьшить значениямассива пошагово до заданного количества шагов.Мы можем уменьшить элементы массива только в том случае, если текущий элемент больше, чем последний элемент + 1, т. Е. 

if (arr[i]>arr[i-1]+1)
      arr[i] -= 1

мы должны выполнить эту итерацию до тех пор, пока требуемое количество шагов или пока элементы массива не станут непрерывными.

Мы не уменьшаем дальше, если значение массива было уменьшено до его индекса.
например,
[1, 4, 6, 7, 9, 10, 11, 12, 13, 15]


Step-1
[1, 3, 5,7, 8, 10, 11, 12, 13, 14]
(мы не уменьшили 1, поскольку его значения совпадают с его индексом, затем мы уменьшили 4 до 3, поскольку последний элемент равен 1, 4> 1 + 1,аналогично для 6. Но для 7, поскольку условие 7> 6 + 1 не выполняется, поэтому мы не уменьшаем его.)

Step-2
[1, 2, 4, 6, 8, 10,11, 12, 13, 14]

Step-3
[1, 2, 3, 5, 7, 9, 11, 12, 13, 14]

Step-4
[1, 2, 3, 4, 6, 8, 10, 12, 13, 14]

Step-5
[1, 2, 3, 4, 5, 7, 9, 11, 13, 14]

Step-6
[1, 2, 3, 4, 5, 6, 8, 10, 12, 14]

Step-7
[1, 2, 3, 4, 5, 6, 7, 9, 11, 13]

Step-8
[1, 2, 3, 4, 5, 6, 7,8, 10, 12]

Step-9
[1, 2, 3, 4, 5, 6, 7, 8, 9, 11]

Step-10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]


Меня просят вернуть массив на K-м шаге.если K> шаг, когда элементы массива становятся непрерывными, то возвращаются непрерывные.В приведенном выше примере, если K = 20, мы вернем массив из шага 10.

Я написал скрипт на Python, но он не работает для тестовых данных.Это занимает слишком много времени.Может ли кто-нибудь предоставить более оптимизированное решение проблемы. 

def reduce(arr):
    crr = []
    for i in range(1, len(arr)+1):
        if arr[i-1]!=i and arr[i-2]!=arr[i-1]-1:
            crr.append(arr[i-1]-1)
        else:
            crr.append(arr[i-1])
    return crr


brr = [int(i) for i in input().split()]
k = int(input())


goal = list(range(len(brr)))
while k!=0 and brr!=goal:
    k -= 1
    brr = reduce(brr)
print(brr)

Ввод:
обр = 1 4 6 7 9 10 11 12 13 15
k = 7

Вывод моего кода:

[1, 2, 3, 4, 5, 6, 7, 9, 11, 13]

...