javascript - 如何在一个简单的数组上实现空间 trim

Question

这更像是一道伪代码题。 假设我们有一个 char 数组，其中每个值都是一个字母或一个空格。我们需要实现的是一种用单个空格替换任何空格序列的算法。

例子:

数组:

['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);