Можете ли вы сделать это на месте с затратами O(1) на пространство?
Предложение в обратном порядке
Вам задан массив символов arr
, состоящий из последовательностей символов, разделенных пробелами. Каждая последовательность символов, разделенная пробелами, определяет слово.
Реализуйте функцию reverseWords
, которая меняет порядок слов в массиве на противоположный наиболее эффективным образом.
Объясните свое решение и проанализируйте его временные и пространственные сложности.
Пример:
input: arr = [ 'p', 'e', 'r', 'f', 'e', 'c', 't', ' ', 'm', 'a', 'k', 'e', 's', ' ', 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e' ]
output: [ 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e', ' ', 'm', 'a', 'k', 'e', 's', ' ', 'p', 'e', 'r', 'f', 'e', 'c', 't' ]
Ограничения:
- [лимит времени] 5000 мс
- [ввод] массив.символ
arr
- 0 ≤ длина записи ≤ 100
- [выход] array.character
Чтобы сделать это на месте и с космической сложностью O (1). Мы можем
- сначала перевернуть весь массив
- перевернуть каждое из слов:
Временная сложность: двойной обход массива с постоянным числом действий для каждого элемента является линейным O(N)
.
Пространственная сложность: использование индексов итерации и одной временной переменной требует постоянной памяти O(1)
.