方法一：双重遍历

双重遍历是最容易想到的去重方案：

构建一个新的数组存放结果for循环中每次从原数组取出一个元素，用这个元素循环与结果数组对比若结果数组中没有该元素，则存到结果数组中 Array.prototype.unique=function(){ // 构建一个新数组，存放结果 var newArray = [this[0]]; for (var i = 0; i<this.length; i++){ var repeat = false; for(var j=0;j<newArray.length;j++){ if(this[i]===newArray[j]){ repeat=true; break; } } if(!repeat){ newArray.push(this[i]); } } return newArray; } 优点：思路简单、容易实现，用于去重的比较部分是自己编写实现（this[i]==newArray[j]）。可以针对具体情况加以特殊处理。缺点：时间复杂度高，性能差。

以下面这个测试案例进行比较：

function test () { var arr = []; for (var i = 0; i < 1000000; i++) { arr.push(Math.round(Math.random(i) * 10000)); } doTest(arr, 1); } function doTest(arr, n) { var tStart = (new Date()).getTime(); var re = arr.unique(); var tEnd = (new Date()).getTime(); console.log('双重循环去重方法使用时间是:' + (tEnd - tStart) + 'ms'); return re; } test();

在Chrome控制台中测试方法一，花费时间为：4006ms。

方法二：排序遍历去重

先使用sort()方法对原数组做一个排序，排完序之后对数组做遍历，并且检查数组中的第i个元素与结果数组中最后一个元素是否相同。如果不同，则将元素放到结果数组中。

Array.prototype.unique = function () { // 原数组先排序 this.sort(); // 构建一个新数组存放结果 var newArray = []; for (var i = 1; i < this.length; i++) { // 检查原数组中的第i个元素与结果中的最后一个元素是否相同 // 因为排序了，所以重复元素会在相邻位置 if(this[i] !== newArray[newArray.length - 1]) { // 如果不同，将元素放到结果数组中 newArray.push(this[i]); } } return newArray; } 优点：速度快，只需要700ms缺点：去重后的数组会做排序、去重后的数组，与数字相同的数字字符无法区分，比如'12'和12

方法三：对象键值对法

这种方法是利用了对象的key不可以重复的特性来进行去重。

创建一个JavaScript对象及新数组使用for循环遍历原数组，每次取出一个元素与JavaScript对象的键做对比如果不包含，将存入对象的元素值推入到结果数组中，并且将存入对象的该key的value设为1 Array.prototype.unique=function() { var ret = []; var len = this.length; var tmp = {}; for(var i=0; i<len; i++){ if(!tmp[this[i]]){ tmp[this[i]] = 1; ret.push(this[i]); } } return ret; } 优点：速度快，只需要10ms缺点：去重后的数组，与数字相同的数字字符无法区分，比如'12'和12,因为对象key只能为字符串；无法处理复杂数据类型，比如对象（因为对象作为key会变成[object Object]）；特殊数据，比如'proto'会挂掉，因为tmp对象的'proto'属性无法被重写

基于上面提到的缺点，有人提出了以下的改进措施：

Array.prototype.unique=function() { var ret = []; var len = this.length; var tmp = {}; var tmpKey; for(var i=0; i<len; i++){ tmpKey = typeof this[i] + JSON.stringify(this[i]); if(!tmp[tmpKey]){ tmp[tmpKey] = 1; ret.push(this[i]); } } return ret; }

这个改进方法可以弥补上述提到的缺点，但是性能有所降低，去重速度达到了500ms左右，且内存占用较高，但依然是各个方案中最快的。

方法四：Map Key

ES2015中添加了Map这种新的数据类型，可以把它想象成key类型没有限制的对象，它的存取使用单独的get()、set()接口。与传统的对象相比，Map的key在使用中没有限制。

Array.prototype.unique=function() { var ret = []; var len = this.length; var tmp = new Map(); for(var i=0; i<len; i++){ if(!tmp.get(this[i])){ tmp.set(this[i], 1); ret.push(this[i]); } } return ret; } 优点：执行速度快，43ms。缺点：兼容性不高。

方法五：Set

除了Map以外，ES2015还引入了一种叫作Set的数据类型。它不允许重复元素出现。

Array.prototype.unique=function(){ var set = new Set(this); return Array.from(set); } 优点：代码简单，执行速度较快，600ms左右。缺点：兼容性不高。

总结

去重的方法没有最正确的，也没有最优，应该具体问题具体分析，根据实际场景进行选择正确的方法。

请使用手机"扫一扫"x