如何在简单数组上实现 space 修剪

Question

这更像是一道伪代码题。假设我们有一个 char 数组，其中每个值要么是一个字母，要么是一个 space。我们需要实现的是一种算法，它用单个 space.

替换任何 space 序列

示例：

数组：

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

应该变成：

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

这个算法应该只修改给定的数组，而不是在临时数组或类似的东西中使用。更改数组的唯一方法是通过索引设置项目（不能使用任何花哨的数组函数，如 arr.remove(0, 2)，只能使用 arr[i] = b）。 O(n) 有解决方案吗？

任何能够回答这些限制的伪代码或真正的编程语言解决方案都是好的。

Answer 1

为此，您可以在字符串上使用正则表达式替换；

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

Answer 2

除了用于迭代数组的普通索引 i 之外，您还可以使用另一个索引，此处 l 用于为最后一个有效字符保留最后一个新索引。如果最后一个索引实际上没有 space 或没有 space 可用，则会发生值的移动并增加最后一个索引。

数组内部增加索引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);

如何在简单数组上实现 space 修剪

How to implement space trimming on a simple array

javascript

arrays

algorithm

pseudocode

mutable