Можете ли вы сделать это на месте с затратами 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).