← Все вопросы
Как развернуть массив на месте, не создавая новый список?
12
Знаю про a[::-1] и reversed(), но они создают новую последовательность. Хочу развернуть именно сам список in-place, без лишней памяти — как в задачах на собеседовании. Как это делается?
3 ответа
22
✓ Принятый ответ — помог автору
Метод двух указателей: один с начала, другой с конца, меняем элементы местами и сходимся к центру. O(n) времени, O(1) дополнительной памяти.
def reverse_in_place(a):
i, j = 0, len(a) - 1
while i < j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
x = [1, 2, 3, 4, 5]
reverse_in_place(x)
print(x) # [5, 4, 3, 2, 1]
Именно такой код от тебя и хотят на собесе, когда говорят «разверни без срезов». А в обычном коде, конечно, проще a.reverse() — он тоже работает на месте.
Иван Белов Кстати, встроенный list.reverse() как раз делает это in-place и за O(n). · 19 месяцев назад
10
a.reverse() — разворачивает сам список без копии. Если просят руками — два указателя навстречу.
5
a.reverse().
Ваш ответ
Войдите, чтобы ответить на вопрос.
