解锁多种JavaScript数组去重姿势
JavaScript数组去重,一个老生常谈的问题了,但这次是解锁多种JavaScript数组去重姿势。
对以下所有的实现算法,都使用以下代码进行粗略测试:
const arr = []; // 生成[0, 100000]之间的随机数 for (let i = 0; i < 100000; i++) { arr.push(0 + Math.floor((100000 - 0 + 1) * Math.random())) } // ...实现算法 console.time('test'); arr.unique(); console.timeEnd('test');
双重循环
双重循环去重实现比较容易。
实现一:
Array.prototype.unique = function () { const newArray = []; let isRepeat; for (let i = 0; i < this.length; i++) { isRepeat = false; for (let j = 0; j < newArray.length; j++) { if (this[i] === newArray[j]) { isRepeat = true; break; } } if (!isRepeat) { newArray.push(this[i]); } } return newArray; }
实现二:
Array.prototype.unique = function () { const newArray = []; let isRepeat; for (let i = 0; i < this.length; i++) { isRepeat = false; for (let j = i + 1; j < this.length; j++) { if (this[i] === this[j]) { isRepeat = true; break; } } if (!isRepeat) { newArray.push(this[i]); } } return newArray; }
基于思路二的写法改进版,实现三:
Array.prototype.unique = function () { const newArray = []; for (let i = 0; i < this.length; i++) { for (let j = i + 1; j < this.length; j++) { if (this[i] === this[j]) { j = ++i; } } newArray.push(this[i]); } return newArray; }
经过测试代码测试的时间如下:
test1: 3688.440185546875ms test2: 4641.60498046875ms test3: 17684.365966796875ms
Array.prototype.indexOf()
基本思路:如果索引不是第一个索引,说明是重复值。
实现一:
- 利用Array.prototype.filter()过滤功能
- Array.prototype.indexOf()返回的是第一个索引值
- 只将数组中元素第一次出现的返回
- 之后出现的将被过滤掉
Array.prototype.unique = function () { return this.filter((item, index) => { return this.indexOf(item) === index; }) }
实现二:
let arr = [1, 2, 3, 22, 233, 22, 2, 233, 'a', 3, 'b', 'a']; Array.prototype.unique = function () { const newArray = []; this.forEach(item => { if (newArray.indexOf(item) === -1) { newArray.push(item); } }); return newArray; }
经过测试代码测试的时间如下: test1: 4887.201904296875ms test2: 3766.324951171875ms
Array.prototype.sort()
基本思路:先对原数组进行排序,然后再进行元素比较。
实现一:
Array.prototype.unique = function () { const newArray = []; this.sort(); for (let i = 0; i < this.length; i++) { if (this[i] !== this[i + 1]) { newArray.push(this[i]); } } return newArray; }
经过测试代码测试的时间如下: test: 4300.39990234375ms
实现二:
Array.prototype.unique = function () { const newArray = []; this.sort(); for (let i = 0; i < this.length; i++) { if (this[i] !== newArray[newArray.length - 1]) { newArray.push(this[i]); } } return newArray; }
经过测试代码测试的时间如下:
test1: 121.6259765625ms test2: 123.02197265625ms
Array.prototype.includes()
Array.prototype.unique = function () { const newArray = []; this.forEach(item => { if (!newArray.includes(item)) { newArray.push(item); } }); return newArray; }
经过测试代码测试的时间如下:
test: 4123.377197265625ms
Array.prototype.reduce()
Array.prototype.unique = function () { return this.sort().reduce((init, current) => { if(init.length === 0 || init[init.length - 1] !== current){ init.push(current); } return init; }, []); }
经过测试代码测试的时间如下:
test: 180.401123046875ms
对象键值对
基本思路:利用了对象的key不可以重复的特性来进行去重。
但需要注意:
- 无法区分隐式类型转换成字符串后一样的值,比如 1 和 '1'
- 无法处理复杂数据类型,比如对象(因为对象作为 key 会变成 [object Object])
- 特殊数据,比如 'proto',因为对象的 proto 属性无法被重写
解决第一、第三点问题,实现一:
Array.prototype.unique = function () { const newArray = []; const tmp = {}; for (let i = 0; i < this.length; i++) { if (!tmp[typeof this[i] + this[i]]) { tmp[typeof this[i] + this[i]] = 1; newArray.push(this[i]); } } return newArray; }
解决第二点问题,实现二: Array.prototype.unique = function () { const newArray = []; const tmp = {}; for (let i = 0; i < this.length; i++) { // 使用JSON.stringify()进行序列化 if (!tmp[typeof this[i] + JSON.stringify(this[i])]) { // 将对象序列化之后作为key来使用 tmp[typeof this[i] + JSON.stringify(this[i])] = 1; newArray.push(this[i]); } } return newArray; }
经过测试代码测试的时间如下:
test1: 113.849365234375ms test2: 157.030029296875ms
Map
实现一:
Array.prototype.unique = function () { const newArray = []; const tmp = new Map(); for(let i = 0; i < this.length; i++){ if(!tmp.get(this[i])){ tmp.set(this[i], 1); newArray.push(this[i]); } } return newArray; }
实现二:
Array.prototype.unique = function () { const tmp = new Map(); return this.filter(item => { return !tmp.has(item) && tmp.set(item, 1); }) }
经过测试代码测试的时间如下:
test1: 27.89697265625ms test2: 21.945068359375ms
Set
Array.prototype.unique = function () { const set = new Set(this); return Array.from(set); }
Array.prototype.unique = function () { return [...new Set(this)]; }
经过测试代码测试的时间如下:
test1: 36.8046875ms test2: 31.98681640625ms
总结
除了考虑时间复杂度外、性能之外,还要考虑数组元素的数据类型(例如下面的例子)等问题权衡选择出采用哪种算法,例如:
const arr = [1, 1, '1', '1', 0, 0, '0', '0', undefined, undefined, null, null, NaN, NaN, {}, {}, [], [], /a/, /a/];
经过综合考虑,最优的数组去重算法是采用Map数据结构实现的算法。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
一名90后二流大学程序员的自述:我是如何从“菜鸟”到“辣鸡”的
本文来自“摩卡先生”的投稿,通过文字感受一下新手程序员强烈的奋斗激情。 1、编者注 读过本文,能感受到作者作为典型90后不羁的一样,但文字内容远非作者自我调侃的那样从“菜鸟”到“辣鸡”。此文文笔流畅、思路清晰、主次明确,作者有激情且谦虚好学,这都是作为程序员该有的典型特质,希望同样迷茫的技术同行能通过本文,重拾初心、勇往直前! (本文同步发布于:http://www.52im.net/thread-1645-1-1.html) 2、正文引言 人们总是一边不相信鸡汤,一边又奢望鸡汤在关键时刻能够拉自己一把。 成功者不会把那些努力的过程一五一十说出来,因为那些东西太阴暗、太痛苦了。 我当时的苦逼程度,只有我自己最懂。 3、嗨,我是“积极废人” Hi,我是摩卡先生,现在是一所二流学院的大二学生。 刚进入大学时,我对于未来,自己想要走哪条路,真的没有考虑那么多。也不会考虑这么多。 想得更多的是社团啊,学生会啊,怎样才能做得更好,表现好点。那时的自己,可以说是“积极废人”,积极玩游戏,什么都不会的人... 每次上完课,就像脱缰的野马,回到宿舍就是玩NBA2K、火影忍者,玩到根本停不下来,除了吃饭...
- 下一篇
前端之jquery函数库
jquery介绍 jQuery是目前使用最广泛的javascript函数库。据统计,全世界排名前100万的网站,有46%使用jQuery,远远超过其他库。微软公司甚至把jQuery作为他们的官方库。 jQuery的版本分为1.x系列和2.x、3.x系列,1.x系列兼容低版本的浏览器,2.x、3.x系列放弃支持低版本浏览器,目前使用最多的是1.x系列的。 jquery是一个函数库,一个js文件,页面用script标签引入这个js文件就可以使用。 <script type="text/javascript" src="js/jquery-1.12.2.js"></script> jquery的口号和愿望 Write Less, Do More(写得少,做得多) 1、http://jquery.com/官方网站2、https://code.jquery.com/版本下载 jquery文档加载完再执行 将获取元素的语句写到页面头部,会因为元素还没有加载而出错,jquery提供了ready方法解决这个问题,它的速度比原生的 window.onload 更快。 <sc...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- Windows10,CentOS7,CentOS8安装Nodejs环境
- CentOS8编译安装MySQL8.0.19
- CentOS6,CentOS7官方镜像安装Oracle11G
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- 设置Eclipse缩进为4个空格,增强代码规范
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题