Как реализовать обрезку пространства на простом массиве

Question

Это скорее вопрос с псевдокодом.Допустим, у нас есть массив символов, где каждое значение является либо буквой, либо пробелом.Нам нужно реализовать алгоритм, который заменяет любую последовательность пробелов одним пробелом.

Пример:

массив:

['a', 'b', ' ', ' ', ' ', 'b', 'c', ' ']

должен стать:

['a', 'b', ' ', 'b', 'c', ' ']

Этот алгоритм должен только модифицировать данный массив и не использовать его во временных массивах или в чем-либо подобном.Единственный способ изменить массив - это установить элементы по индексу (нельзя использовать какую-либо необычную функцию массива, такую ​​как arr.remove(0, 2), используйте только arr[i] = b).Есть ли решение в O (n)?

Хорошо подходит любое решение с псевдокодом или реальным языком программирования, которое отвечает ограничениям.

Answer 1

Вы можете взять помимо обычного индекса i для итерации массива другой индекс, здесь l для хранения последнего нового индекса для последнего действительного символа.Если на самом деле нет ни пробела, ни пробела в последнем индексе, то происходит смещение значения и последний индекс увеличивается.

Внутри массива увеличивается индекс i.

Наконец, настройте длину массива на l.

 i    l    0  1  2  3  4  5  6  7
--   --   -----------------------
           a  b  _  _  _  b  c  _
 0    0    a
 1    1    a  b
 2    2    a  b  _
 3    2    a  b  _
 4    2    a  b  _
 5    3    a  b  _  b
 6    4    a  b  _  b  c
 7    5    a  b  _  b  c  _

var array = ['a', 'b', ' ', ' ', ' ', 'b', 'c', ' '],
    i = 0,
    l = 0;
    
while (i < array.length) {
    if (array[i] !== ' ' || array[l - 1] !== ' ') {
        array[l] = array[i];
        l++;
    }
    i++;
}

array.length = l;

console.log(array);

Answer 2

Для этого вы можете использовать заменить на регулярное выражение в строке;

arr.join('').replace(/\s+/g, ' ').split('')