如何移除数组中连续重复元素（理想O(n)时间复杂度）

我们需要实现的是移除数组中连续重复的后续元素——仅保留每组连续重复元素的第一个，而非去掉所有重复元素。比如输入：
[1, 2, 2, 3, 3, 1, 1, 4, 5, 5, 4, 4, 4, 6, 2]
输出应为：
[1, 2, 3, 1, 4, 5, 4, 6, 2]

注意：[...new Set(items)]会直接生成全唯一元素的数组，不符合需求：[1, 2, 3, 4, 5, 6]

以下是几种O(n)时间复杂度的实现方式：

方法一：普通遍历法 #

这是最直观的实现，遍历一次数组，将非连续重复的元素存入结果数组：

function removeConsecutiveDuplicates(items) {
  if (!items.length) return [];
  const result = [items[0]];
  for (let i = 1; i < items.length; i++) {
    if (items[i] !== result[result.length - 1]) {
      result.push(items[i]);
    }
  }
  return result;
}

// 测试示例
const input = [1, 2, 2, 3, 3, 1, 1, 4, 5, 5, 4, 4, 4, 6, 2];
console.log(removeConsecutiveDuplicates(input));
// 输出: [1, 2, 3, 1, 4, 5, 4, 6, 2]

• 时间复杂度：O(n)，每个元素仅遍历一次
• 空间复杂度：O(n)，需要额外存储结果数组

方法二：使用Array.reduce简化实现 #

利用reduce方法的累加器特性，逻辑和遍历法一致，写法更简洁：

function removeConsecutiveDuplicates(items) {
  return items.reduce((acc, curr) => {
    if (acc.length === 0 || curr !== acc[acc.length - 1]) {
      acc.push(curr);
    }
    return acc;
  }, []);
}

// 测试示例
const input = [1, 2, 2, 3, 3, 1, 1, 4, 5, 5, 4, 4, 4, 6, 2];
console.log(removeConsecutiveDuplicates(input));
// 输出: [1, 2, 3, 1, 4, 5, 4, 6, 2]

• 时间复杂度：O(n)，本质仍是一次遍历
• 空间复杂度：O(n)

方法三：双指针原地修改（空间优化） #

如果允许修改原数组，可以用双指针法将空间复杂度降到O(1)（仅使用常量额外空间）：

function removeConsecutiveDuplicates(items) {
  if (!items.length) return [];
  let pointer = 0;
  for (let i = 1; i < items.length; i++) {
    if (items[i] !== items[pointer]) {
      pointer++;
      items[pointer] = items[i];
    }
  }
  // 截断数组到有效元素长度
  items.length = pointer + 1;
  return items;
}

// 测试示例
const input = [1, 2, 2, 3, 3, 1, 1, 4, 5, 5, 4, 4, 4, 6, 2];
console.log(removeConsecutiveDuplicates(input));
// 输出: [1, 2, 3, 1, 4, 5, 4, 6, 2]

• 时间复杂度：O(n)
• 空间复杂度：O(1)，直接在原数组上修改，无需额外存储结果数组

内容的提问来源于stack exchange，提问作者Parzh