推荐关注 Meteor JSLint - a Javascript code quality tool jsFiddle D3.js WebStorm 推荐书目 Javascript 权威指南第 5 版
Closure: The Definitive Guide
Closure: The Definitive Guide 
这是一个创建于 3569 天前的主题，其中的信息可能已经有所发展或是发生改变。
本文原发布在 segmentfault.com https://segmentfault.com/a/1190000004548931 在学是作者，现在贴到 V2EX ，所以不存在侵权。
前言
最近为了换工作，准备下面试，开始回顾复习 Javascript 相关的知识，昨天下午想到了数组去重的相关方法，干脆整理出几篇 Javascript 算法文章，以备后用，此系列文章不定篇数，不定时间，想到哪写到哪，不保证正确性，不保证高效率，只是谈谈个人理解，如有错误，请诸位斧正。
关于去重
数组去重是一个比较常见的算法考察点，实现去重的方式无外乎通过唯一性和非唯一性。简单来讲就是挑出唯一的或者删除不唯一的。以下所有算法都是我自己瞎命名的，请无视之。
循环匹配去重
顾名思义，就是把数组中的每一个元素都和存放元素的数组对比，遇到不重复的元素，放入新数组中，直至循环结束，由于匹配也有循环，也可以称为双循环匹配去重，这也是大家都能想到的最简单的方式。
实现代码：
var arr=[1,3,4,56,3,7,9,7]; var result=[]; //匹配 function isMatch(array,n){ for(var i=0;i<array.length;i++){ if(array[i]==n){ return true; } } return false; }; //验证所有元素 function unqiue(array){ for(var i=0;i<array.length;i++){ if(!isMatch(result,array[i])){ result.push(array[i]); } } return result; }; console.log(unqiue(arr)); 注意：上面方法有一个 bug ，当存在数字和数字形式的字符串的时候，没有区分出数字和数字字符串。因为在匹配函数 isMatch()里用的是双等“==”，没有验证元素类型，实际应该使用全等“===”。 修改后的代码如下：
var arr=[1,3,4,56,3,'1',7,9,7]; var result=[]; //匹配 function isMatch(array,n){ for(var i=0;i<array.length;i++){ if(array[i]===n){ return true; } } return false; }; //验证所有元素 function unqiue(array){ for(var i=0;i<array.length;i++){ if(!isMatch(result,array[i])){ result.push(array[i]); } } return result; }; console.log(unqiue(arr)); 算法优缺点：
优点:
- 实现简单，思路直观
缺点：
- 效率低下
JSON 去重 /对象去重 /字典去重 1
JSON 去重，简单来讲就是利用 Object 对象 key 的唯一性，将数组的元素转换为 JSON 或者说对象的 key 值。 JSON 的 value 存储数组的索引 index ，然后对 JSON 对象进行 for in 循环，存储到新数组中。
Array 、 JSON 、{}都是 Object ，所以采用任意一种都可以实现此算法。
实现代码：
Array 方式：
var arr=[1,3,4,56,3,'1',7,9,7]; function unqiue(array){ var cache=[]; var result=[]; //将数组元素转为对象的 key for(var i=0;i<array.length;i++){ cache[array[i]]=i; }; //存储 key(实际的数组元素) for(key in cache){ result.push(key); }; return result; } console.log(unqiue(arr)); JSON 方式：
```
var arr=[1,3,4,56,3,'1',7,9,7];
function unqiue(array){
var cache={};
var result=[];
//将数组元素转为对象的 key
for(var i=0;i<array.length;i++){
cache[array[i]]=i;
};
//存储 key(实际的数组元素) for(key in cache){ result.push(key); }; return result; }
console.log(unqiue(arr));
```
Object 方式：
var arr=[1,3,4,56,3,'1',7,9,7]; function unqiue(array){ var cache=new Object(); var result=[]; //将数组元素转为对象的 key for(var i=0;i<array.length;i++){ cache[array[i]]=i; }; //存储 key(实际的数组元素) for(key in cache){ result.push(key); }; return result; } console.log(unqiue(arr)); 算法优缺点：
优点:
- 简单
- 效率非常高
缺点:
1.改变了数组元素的类型（去重后的元素都为字符串类型）
2.无法区分数字和数值型字符串
JSON 去重 /对象去重 /字典去重 2
第 2 种方式和第 1 种方式在本质上没有太多区别，反而因为做了判断，效率降低了一点点。
实现代码
var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7]; function unqiue(array){ var cache={}; var result=[]; for(var i=0;i<array.length;i++){ //如果 json 或者是或 hash 里没有 if(!cache[array[i]]){ result.push(array[i]); //设置当前结果为已存在 cache[array[i]]=true; } } return result; } console.log(unqiue(arr)); 为什么说第 2 种方式和第一种方式没有本质的区别呢？第 2 种方式有一个临时的 hash 表 cache ，存储了最终结果 result 中是否存在对应元素记录。如果 cache 中的记录不存在，说明该数组元素没有重复。第 1 种方式没有做判断，因为 json 数组，对象等，本质就可以看做是 hash ， cache[array[i]]中 array[i]相同的只会存在一个，所以不需要做判断。这也是第 1 种更快一点点的原因,虽然效率没有第 1 种那么高，但这种方式引入了一种解决第 1 种方式 bug 的潜在方案，在为 Array 添加去重方式的时候会提到这个方案。
算法优缺点：
优点：
- 效率很高
缺点:
- 无法区分数字和数值型字符串
队尾递归去重
昨天晚上思忖良久想到用队列的方式，先将数组排序成升序或降序的队列，这样相同的元素就处在一个区域内，然后从队尾向前匹配，如果匹配成功，删除队尾，然后前一个元素再向其面的匹配。整个匹配完成之后，剩下的元素就是去重过后的队列。
var arr=[6, 4, 6, 9, '6', 13, 56, 9, ,'11',1, 8, '7', 17, 5, 45, 3, 7]; function unqiue(array){ //排序数组，形成队列 array.sort(function(m,n){return m-n;}); ////排序后，队尾向前对比，如果相同，删除队尾，依次类推 function loop(Index){ if(Index>=1){ if(array[Index]===array[Index-1]){ arr.splice(Index,1); } loop(Index-1); } } loop(array.length-1); return array; } console.log(unqiue(arr)); 算法优缺点：
优点：
- 效率较高
缺点:
- 没有保留原数组的顺序
indexOf 去重 1
ECMAScript5 为数组添加了两个位置方法： indexOf()和 lastIndexOf()。如果查找不到相应的数组元素，返回-1 。所以可以使用 indexOf 方式来去重。
实现代码：
var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7]; function unqiue(array){ var result=[]; for(var i=0;i<array.length;i++){ if(result.indexOf(array[i])==-1){ result.push(array[i]); } } return result; } console.log(unqiue(arr)); 优点：
- 效率较高
缺点：
2. 不兼容低版本浏览器（ ECMAScript5 才支持 indexOf()和 lastIndexOf()方法）
indexOf 去重 2
从上面的 indexOf 去重扩展开来，如果用 indexOf 查找一个数组的元素的结果不是该数组元素的索引，那么可以认为这个数组出现过。所以这也可以用来实现数组去重。
var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7]; function unqiue(array){ var result=[]; for(var i=0;i<array.length;i++){ if(array.indexOf(array[i])==i){ result.push(array[i]); } } return result; } console.log(unqiue(arr)); 其实循环判断可以从第 1 项开始，因为第 0 项肯定不会重复。
优点：
- 效率较高
缺点：
2. 不兼容低版本浏览器（ ECMAScript5 才支持 indexOf()和 lastIndexOf()方法）
为 Array 对象添加去重方法的坑
以上总结了几种去重方法，我们来个小例子为 Array 对象添加去重，方便直接调用，实际情况下我们是不推荐修改 Javascript 原生对象的，容易造成污染或者不可控的情况的发生。
以 JSON 去重 1 的方式为 Array 添加对象，我们选用了“ cache=[]”的那种，结果不小心踩到了大坑。
```
var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];
Array.prototype.unqiue=function(){
var cache=[];
var result=[];
for(var i=0;i<this.length;i++){
cache[this[i]]=i;
}
for(key in cache){ result[cache[key]]=key; } return result; }
console.log(arr.unqiue());
```
结果居然把 Array 本身的 unqiue 方法也当做数组的内容输出出来了。
再对比下使用 JSON 或者对象的方式的结果
```
var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];
Array.prototype.unqiue=function(){
var cache={};
var result=[];
for(var i=0;i<this.length;i++){
cache[this[i]]=i;
}
for(key in cache){ result[cache[key]]=key; } return result; }
console.log(arr.unqiue());
```
结果是正常的。
所以，我们在向 Array 对象添加去重方法时，不能使用[]的方式，要使用 JSON 或者空对象的方式，但是依然无法区分数值和数值型字符串。
JSON 去重 3
在 JSON 去重 2 我们判断的是 cache[array[i]]值是否为真。 cache[array[i]]这种实际是当做 cache 的自定义属性存储的， array[i]被转成了字符串形式，也同样存在无非区分数值和数值型字符串的情况，所以我们需要对 JSON 方式 2 进行改造。
代码如下:
var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7]; function unqiue(array){ var cache={}; var result=[]; for(var i=0;i<array.length;i++){ var record=typeof(array[i])+array[i]; //如果 json 或者是或 hash 里没有 if(!cache[record]){ result.push(array[i]); //设置当前结果为已存在 cache[record]=true; } } return result; } console.log(unqiue(arr)); 相比于 JSON 去重 2 ，我们对判断条件做了修改， cache[array[i]]存在数值和数值字符串时[array[i]]相同的情况，但是[typeof(array[i])+array[i]]却不存在这种情况，数值的 typeof 为 number ，数值字符串的 typeof 为 string ，区分开了这两种情况。
所以最终我们为 Array 对象添加的是这样的去重方法
var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7]; Array.prototype.unqiue=function(){ var cache={}; var result=[]; for(var i=0;i<this.length;i++){ var record=typeof(this[i])+this[i]; //如果 json 或者是或 hash 里没有 if(!cache[record]){ result.push(this[i]); //设置当前结果为已存在 cache[record]=true; } } return result; } console.log(arr.unqiue()); 补充队列去重方式
从网友哪里知道另外的两种队列方式，代码如下，原理和我写的队尾递归去重类似，代码如下：
队尾去重
var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7]; function unqiue(array){ var result=[]; array.sort(function(m,n){return m-n}); for(var i=0;i<array.length;i++){ if(array[i]!==result[result.length-1]){ result.push(array[i]); } } return result; } console.log(unqiue(arr)); 队首去重
var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7]; function unqiue(array){ var result=[]; array.sort(function(m,n){return n-m}); for(var i=0;i<array.length;i++){ if(array[i]!==result[0]){ result.unshift(array[i]); } } return result; } console.log(unqiue(arr)); 附言：
关于 Javascript 数组去重的方式基本就总结到这里了，欢迎在评论里指出错误和贡献其他方法。
 | 1 otakustay 2016-03-07 17:16:19 +08:00  1 咱们直接用 Map 类就好了嘛…… |
 | 2 sumhat 谈到算法效率的时候，请给出时空复杂度。 |
 | 3 O3YwA1ENkb7i35XJ 2016-03-07 17:25:41 +08:00 1 我想说的是: 楼主居然分不清 `JSON` 和 `Object`, 以及居然不知道 `{}` 是 `new Object` 的缩写. 居然单独把 var cache = {} 做为 `JSON` 拿来讲. |
 | 4 markowitz73 2016-03-07 17:34:21 +08:00 如果不保证效率，那么算法有什么意义呢？ |
 | 5 holyghost 2016-03-07 17:37:25 +08:00 咱们直接用 Set 类就好了嘛…… |
 | 6 ChiChou 2016-03-07 17:46:22 +08:00 我也想吐槽 JSON 这个说法 |
 | 7 sampeng 2016-03-07 17:55:29 +08:00 特意来登陆吐槽 JSON 的。。 用同样的时间做去重，用 map ，只是消耗现代机器无视的内存占用来去重。可以最少比你多写 3 个函数了。。。 |
 | 8 jsonline 2016-03-07 18:03:54 +08:00 via Android JSON 是哪四个单词的全称楼主 |
 | 9 learnshare 2016-03-07 18:08:05 +08:00 JSON 是文件格式 /文本格式吧 `!cache[array[i]]` 不能用来判断 `value == false` 的情况 |
 | 10 daysv 2016-03-07 18:11:12 +08:00 [ 1, 1, 'a', 'a' ].filter( (el, i, arr) => arr.indexOf(el) === i); Array.from( new Set([ 1, 1, 'a', 'a' ]) ); 一般这样就好了吧，搞的长篇大论啊？？ |
 | 11 codespots OP 统一回复下 JSON 的问题，这个确实是我失误没有说清楚，本来只是用比较通俗的说法来解释下{}去重的方式，本来想用字典吧，但是字典属于 python 的说法。所以就用了 json 来指代下，因为 json 的 key 也具有唯一性嘛，给各位道歉，至于{}和 new object 缩写我是知道的，以后不敢随便在 V2EX 上发文章了，太可怕了。 |
| 12 codespots OP 至于为什么不用 object 来指代，因为 json 格式比较易于理解，也容易让各位注意到实际上数组元素的类型已经被转换为了字符串，考虑不周，还望见谅。 |
| 13 codespots OP @learnshare !cache[array[i]] 可以判断 value==false 的情况，这里的 false 只是做了新对象的 key ，实际是!cache[“ false ”] @jsonline @sampeng @ChiChou @xqin JSON 是 Javascript Object Notation 的缩写，抱歉啊，才疏学浅，表达不严谨，出了问题，请各位见谅。另外请教各位， V2EX 的帖子怎么删除啊，不敢再误导其他人。吾长见笑于大方之家 |
 | 14 zhujinliang 2016-03-07 19:00:07 +08:00 via iPhone 不先 sort 然后依次比对么？ |
 | 15 v1024 2016-03-07 19:05:43 +08:00 [...new Set([1, 1, 2, 2, 3, "a", "a"])] 搞定。。 |
 | 16 sagnitude 2016-03-07 19:16:37 +08:00 for-in 很慢，数量级级别的慢（除了 IE ），不要用 for-in |
 | 17 jianzong 2016-03-07 19:26:05 +08:00 算法在哪？ |
 | 18 bumz 2016-03-07 19:32:44 +08:00 via iPhone ES6: Array.from(new Set(array).values()) |
 | 20 pupboss 2016-03-07 20:52:17 +08:00 为什么 indexOf 的效率高，求证明，不是找茬 因为我只能想到这一种办法去重了 一直觉得效率很低下 |
 | 22 murmur 2016-03-07 21:20:01 +08:00 map 背后的实现应该是 hashmap 吧? |
| 24 4263Ad06Awk3b1Do 2016-03-07 21:43:19 +08:00 @daysv 说的方法就很好了啊 |
 | 25 xuwenmang 2016-03-07 21:45:54 +08:00 |
 | 26 WittBulter 2016-03-08 04:04:44 +08:00 目前只有 Set 是 O(n)吧... |
 | 27 keyanzhang 2016-03-08 08:56:42 +08:00 const nums = [ 1, 2, 1, 3, 1, 2, 4 ]; const withoutDups = Array.from(new Set(nums)); |
 | 28 vagary 2016-03-08 09:09:47 +08:00 @zhujinliang 鱼爆一地 |
 | 29 xunuoi 2016-03-08 09:46:54 +08:00 调用数组自己的 sort 方法后再做队列排序， sort 本身已经增加了复杂度了，整体效率并不会高 |
| 30 O3YwA1ENkb7i35XJ 2016-03-08 11:00:14 +08:00 |
| 31 codespots OP 感谢各位，我确实有很多不足，谢谢各位，我会努力的，年轻人还是要提高自己的姿势水平！ |
 | 32 Jaylee 2016-03-08 11:44:17 +08:00 23333 年轻人还是要多提高自己的姿势水平再来写文章啊 |
 | 33 neoblackcap 2016-03-08 15:54:22 +08:00 文章其实还好，但是觉得没有深入到根基，其实去重算法我觉得基本上就是基于 hash 的，还有神奇的 bloom-filter,当然也有简单暴力算法。 还有就是改变数据类型这个我觉得不是事吧，你在暴露的接口那里，再转换回去就好了嘛。你算法内部的数据结构怎么会是一个问题呢？关键是你要给出对应的时空复杂度，那才有讨论算法的价值。 |
 | 34 tedzhou 2016-03-08 16:00:11 +08:00 就问一句 indexOf 的时间复杂度是多少？ 还有 lz 列的 n 种写法其实是等效的。。 |
Select Language