Блог

Главная - Вопросы по программированию - Проверьте, делает ли реверсирование вложенного массива массив отсортированным-Python

Проверьте, делает ли реверсирование вложенного массива массив отсортированным-Python

#python #algorithm #list

#python #алгоритм #Список

Вопрос:

 v=[1,2,3,4,8,7,6,9]

В приведенном выше списке реверсирование 6,7,8 даст последовательные значения. Если я правильно понимаю, я думаю, что это то, что хочет найти эта проблема https://www.geeksforgeeks.org/check-reversing-sub-array-make-array-sorted /

Мой подход был

  1. Найдите списки перевернутых значений
  2. Найдите, какой из этих списков содержит последовательный номер.

Я не могу заставить step2 работать. Вот мой код:

 v=[1,2,3,4,8,7,6,9]

ls=[]
# This part below will generate many lists and 1 of them will be [6,7,8]
for i in range (0,len(v)-1):
    for j in range(i 1, len(v)):
        r= v[i:j][::-1]
        ls.append(r)# this append lists not values

#Below code will check to see if any list has consecutive values
for item in ls:
    for i in range(len(item) - 1):
        if item[i]   1 == item[i   1]:
            if i == 0 or item[i] - 1 != item[i - 1]:
                print(item)

Я получаю следующее, когда я ожидал [6,7,8]

 [6, 7, 8, 4, 3]
[7, 8, 4]
[6, 7, 8, 4]
[7, 8]
[6, 7, 8]

Может кто-нибудь любезно дать мне подсказку? Правильно ли я интерпретировал исходный вопрос? Я не хотел использовать geek для ответа geek.

Комментарии:

1. В связанном вопросе нет требования, чтобы отсортированные значения были последовательными числами.

2. Я понимаю, что вы имеете в виду, когда я читаю «Перевернув подмассив {5, 4, 3}, массив будет отсортирован». Я предположил, что числа должны быть последовательными.

3. Хорошо, числа не обязательно должны быть последовательными. Кроме того, вы можете просто использовать 2 указателя, чтобы заставить это работать. Третье решение по ссылке должно сработать для вас.

Ответ №1:

Если вы ищете только одну подстроку для реверсирования, вы можете использовать zip() для сравнения последовательных пар значений. Сначала определите местоположение первой убывающей пары. Затем найдите местоположение первой возрастающей пары с этой точки. Если у вас есть допустимый диапазон, инвертируйте подстроку и проверьте, в порядке ли список.

 a = [1,2,3,4,8,7,6,9]

start        = next( (i for i,(v0,v1) in enumerate(zip(a,a[1:])) if v0>v1),len(a))
end          = next( (i start 1 for i,(v0,v1) in enumerate(zip(a[start:],a[start 1:])) if v0<v1),len(a))
if end > start : a[start:end] = a[start:end][::-1]
canSort      = end > start 1 and not any( a>b for a,b in zip(a,a[1:])) # True

Это будет обрабатываться за O (n) время, в отличие от O (n ^ 2) для вложенных циклов.

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

Ответ №2:

Вы можете сделать что-то вроде этого … предполагая, что под последовательными числами вы подразумеваете числа, которые отличаются на одну единицу. Вы также можете изменить сценарий для размещения чисел в обратном порядке, но не в точном порядке (8 7 6) против (9 6 4)

 v=[1,2,3,4,8,7,6,9]

l = []
last_item =-99
for i in range(1,len(v)-1):
    if  v[i]  == v[i   1]   1:
        l.append(v[i])
        last_item = v[i]
    elif v[i] == last_item - 1:
        l.append(v[i])
        last_item = v[i]
print(sorted(l))
Метки: ,