js数组去重的4个方法+1

时间:2022-11-18 19:01:04
  1. Array.prototype.unique1 = function()
    {
    var n = []; //一个新的临时数组
    for(var i = 0; i < this.length; i++) //遍历当前数组
    {
    //如果当前数组的第i已经保存进了临时数组,那么跳过,
    //否则把当前项push到临时数组里面
    if (n.indexOf(this[i]) == -1) n.push(this[i]);
    }
    return n;
    }
  2. Array.prototype.unique2 = function()
    {
    var n = {},r=[]; //n为hash表,r为临时数组
    for(var i = 0; i < this.length; i++) //遍历当前数组
    {
    if (!n[this[i]]) //如果hash表中没有当前项
    {
    n[this[i]] = true; //存入hash表
    r.push(this[i]); //把当前数组的当前项push到临时数组里面
    }
    }
    return r;
    }

    其中第1种用到了数组的indexOf方法。此方法的目的是寻找存入参数在数组中第一次出现的位置。很显然,js引擎在实现这个方法的时候会遍历数组直到找到目标为止。所以此函数会浪费掉很多时间。 而第2中方法用的是hash表。把已经出现过的通过下标的形式存入一个object内。下标的引用要比用indexOf搜索数组快的多。

    为了判断这两种方法的效率如何,我做了一个测试程序,生成一个10000长度的随机数组成的数组,然后分别用几个方法来测试执行时间。 结果表明第二种方法远远快于其他两种方法。 但是内存占用方面应该第二种方法比较多,因为多了一个hash表。这就是所谓的空间换时间。 

第三种方法:

Array.prototype.unique4 = function()
{
this.sort();
var re=[this[0]];
for(var i = 1; i < this.length; i++)
{
if( this[i] !== re[re.length-1])
{
re.push(this[i]);
}
}
return re;
}

    这个方法的思路是先把数组排序,然后比较相邻的两个值。 排序的时候用的JS原生的sort方法,JS引擎内部应该是用的快速排序吧。 


第二种方法有个局限,就是作为下标会被转换为字符串,这样1, '1'等不同类型的值会对应到同一个下标而被去重,但实际应该保留。

把 hash 表的值从 true 改为一个数组,里面保存出现过的类型就行了。
最终方法:四.

[javascript] view plain copy
  1. Array.prototype.unique = function()  
  2. {  
  3.     var n = {}, r = [], len = this.length, val, type;  
  4.     for (var i = 0; i < this.length; i++) {  
  5.         val = this[i];  
  6.         type = typeof val;  
  7.         if (!n[val]) {  
  8.             n[val] = [type];  
  9.             r.push(val);  
  10.         } else if (n[val].indexOf(type) < 0) {  
  11.             n[val].push(type);  
  12.             r.push(val);  
  13.         }  
  14.     }  
  15.     return r;  
  16. }  
测试:var arr=[];
  for(var i=0;i<1000000;i++){
          arr.push(parseInt(Math.random()*1000));
  }
       console.time("时间");
       arr=arr.unique3();
       console.timeEnd("时间");
       console.log(arr);

第一种:810.859ms

第二种:13.029ms  但存在缺陷

第三种:789.781ms

第四种最终方法;20.117ms

结论:第四种方法快了太多了

还有一种方法利用数组的 filter 方法,可根据条件过滤数组。

var a = [1,2,2,3,4,5,6,7];
var b = a.filter(function(v){
    return v % 2 === 0;
});
console.log(a);  // ->[1,2,2,3,4,5,6,7]
console.log(b);  // ->[2,2,4,6]

数组的 filter 方法,可根据条件过滤数组。
遍历数组,将 filter 的参数 function(v){..} 返回为 false 时的值滤掉,但不改变原数组。

方法五:

var arr = [3,5,2,6,2,3,5,8,6]

function distinct(arr) {
return arr.filter(function (elem,index,arr){
return arr.indexOf(elem,index+1) === -1; //判断当前元素之后没有与之相同的元素,则返回true
});
}

console.log(distinct(arr));
思路很好,但是测试耗时太长居然要8000多ms