去掉数组中连续的数字

这是一道面试题，给大家分享一下：【去掉数组中连续的数字】，我又称之为「数组消消乐」。

题目 #

数组中存储着多个 0-9 的数字，若存在连续大于等于 4 个相同的数字，则将其消除；若消除后，依然有连续个数大于等于 4 的数字，则继续消除。然后返回最终消除完毕后的数组。

实例：

/**

 * @param {number[]} arr

 * @return {number[]}

 */
function eliminate(arr) {}

console.log(eliminate([1, 1, 1, 1, 2]));
// [2]

console.log(eliminate([1, 1, 1, 1, 1, 2]));
// [2]

console.log(eliminate([2, 1, 1, 1, 1, 2, 2, 2]));
// []

console.log(eliminate([1, 1, 1, 0, 0, 0, 0, 0, 1, 2, 2, 3, 3, 3, 3]));
// [2, 2]

解题思路 #

这题根据数组中的数据和数组的长度，有着几个不同的解法。

简单暴力 #

最简单暴力的，就是每次只清除当前连续的数字，等下次循环时，再重新清除新拼接的新数组，直到无法清除为止。

function eliminate(arr) {
  while (true) {
    let start = 0;
    let end = 0;

    for (end = start + 1; end < arr.length; end++) {
      if (arr[end] !== arr[start]) {
        break;
      }
    }
    if (end - start >= 4) {
      arr.splice(start, end);
    } else {
      return arr;
    }
  }
}

但这个时间复杂度太高了，每清除一次，就得从头开始循环。当然，也可以加一些优化措施，比如继续向后查找是否存在连续个数大于等于 4 的数字，但这里尤其要注意一个问题，不能光只删除后面的数字，不管前面的数字。

比如有这样的一个例子：[1,1,1,2,2,2,2,1,1,1,1]，3 个连续的 1，4 个连续的 2，再跟着 4 个连续的 1。若删除了 4 个连续的 2 后，继续向后查找，只删除后续的连续的 4 个 1，是不对的。因为在删除 4 个 2 后，将数据前后拼接后，其实是连续 7 个 1。

利用数组计数器 #

我们可以看到题目中要求的是，数组的每项是 0-9 的数字，数据项不大，完全可以用数组来存储连续的数组个数。下标表示该数字，值表示该数字的连续个数。

function eliminate(arr) {
  const counts = [];

  counts[arr[0]] = {
    start: 0,
    num: 1,
  };

  let i = 1;
  while (i < arr.length) {
    if (arr[i] !== arr[i - 1]) {
      // 当数字不一样时，就需要判断前面的数字的连续的个数
      const { start, num } = counts[arr[i - 1]] || {};

      if (num >= 4) {
        counts[arr[i - 1]].num = 0;

        arr.splice(start, num);
        i = start - 1;
      } else {
        counts[arr[i]] = {
          start: i,
          num: 1,
        };
      }
    } else {
      counts[arr[i]].num++;
    }
    i++;
  }

  const { start, num } = counts[arr[arr.length - 1]];
  if (num >= 4) {
    arr.splice(start, num);
  }
  return arr;
}

利用栈结构 #

这种题目天然适合栈结构，无论数组中是什么数据，均可以压到栈里，顶部的元素永远是当前正在连续计数的数字，当该数字被消除后，则从栈中弹出。

function eliminate(arr) {
  const stack = []; // 每个元素存储的是该元素和连续的个数

  let i = 0;
  while (i < arr.length) {
    const { length } = stack;

    if (!length) {
      // 栈中还没有元素，直接压入
      stack.push({ item: arr[i], num: 1 });
      i++;
    } else if (stack[length - 1].item === arr[i]) {
      // 栈顶的元素与当前元素相等
      stack[length - 1].num++;
      i++;
    } else {
      // 栈顶的元素与当前元素不相等
      if (stack[length - 1].num >= 4) {
        // 连续个数大于等于4，将该数字弹出
        stack.pop();
        // 而且，这里的i并没有加1，因为当前不一样的那个元素还要继续与下一个栈顶的元素进行比较
        // 比如[1, 1, 1, 2, 2, 2, 2, 1]，当栈顶元素2与最后一个1比较，栈弹出2后，最后一个1还得跟新栈顶元素1进行比较
      } else {
        stack.push({ item: arr[i], num: 1 });
        i++;
      }
    }
  }

  if (stack.length && stack[stack.length - 1].num >= 4) {
    stack.pop();
  }
  // 栈里留下来的数据，都是连续个数不够4个的，将栈中的数据拿出来，拼接成新的数组
  let result = [];
  for (let i = 0; i < stack.length; i++) {
    result = result.concat(new Array(stack[i].num).fill(stack[i].item));
  }
  return result;
}

我们利用栈结构先进后出的特性，能很方便地解决这个问题。

总结 #

这道题主要是考察我们对一些数据结构的使用，如果用不好的话，实现起来就麻烦很多，而且时间复杂度也会高很多。