去掉数组中连续的数字

蚊子前端博客
发布于 2023-02-13 22:53
去掉数组中连续的数字,我又称之为「数组消消乐」

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

题目

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

实例:

COPYJAVASCRIPT

/** * @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]

解题思路

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

简单暴力

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

COPYJAVASCRIPT

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 的数字,数据项不大,完全可以用数组来存储连续的数组个数。下标表示该数字,值表示该数字的连续个数。

COPYJAVASCRIPT

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; }

利用栈结构

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

COPYJAVASCRIPT

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; }

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

总结

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

标签:
阅读(279)

公众号:

qrcode

微信公众号:前端小茶馆

公众号:

qrcode

微信公众号:前端小茶馆