JavaScript数组去重的四种实现

1.Set+Array

function uniqueArray( array ){
  return Array.from(new Set(array))
}
时间复杂度:O(N)
空间复杂度:O(N),因为需要一个额外的Set与Array的存储空间

2. splice

function uniqueArray(arr){
  for(var i=arr.length-1;i>=0;i--){
    for(var j=i-1;j>=0;j--){
        if(arr[i] == arr[j]){
            arr.splice(j,1);
        }
    } 
  }
  return arr;
}
时间复杂度:O(N^2),双重循环,频繁的内存操作
空间复杂度:O(1),因为不需要额外的存储空间

3. Array

function uniqueArray(arr){
  var resArr = [];
  for(var i of arr){
    if( resArr.indexOf(i) < 0 ){
        resArr.push(i);
    }
  }
  return resArr;
}
时间复杂度:O(N^2),双重循环,频繁的内存操作
空间复杂度:O(N),因为不需要额外的存储空间

4. Object + Array

function uniqueArray(arr){
  var resObj = {};
  for(var i of arr){
    if( !resObj[i] ){
        resObj[i] = 1;
    }
  }
  return Object.keys(resObj);
}
时间复杂度:O(N),Object[key]是采用hash查找,时间复杂度为O(1)
空间复杂度:O(N)

5. 各种方式比较

//随机生成数算法
function randomData(N) {
   var randomArr = []; 
   for( var i=0; i<N ; i++ ){
     var random = Math.ceil(Math.random() * N);
        randomArr.push(random);
   }  
   return randomArr;
  }
//去重算法函数
function uniqueArray( array ){
  return Array.from(new Set(array))
}
//时间计算
function calTime(arrN){
  var timeLog = [];
  for( var i=0; i< arrN.length ; i++ ){
    var tempArr = randomData(arrN[i]);
    var startDate = new Date().getTime();
    uniqueArray(tempArr);
    var endDate = new Date().getTime();
    timeLog.push( endDate - startDate ) ;
  }
  console.log(timeLog);
  return timeLog;
}
calTime([100,1000,10000]);

按照100,1000,10000等数量级进行比较

numLevel Set + Array splice Array Object + Array
100 0 0 0 0
1000 0 5 3 1
10000 1 235 39 3
100000 15 23431 3648 20
1000000 280 - - 228

总结

1.使用splice去重,随着数量级增大最耗时间。
2.Object + Array去重在大数量级上面表现最好。
3.Array 操作效果明显好于 splice效果

不足

缺少各种方式的详细数据,无法判断在什么情况下使用哪种去重方式最好,希望能够绘制耗费时间折线图

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容