澳门皇冠金沙网站-澳门皇冠844网站

热门关键词: 澳门皇冠金沙网站,澳门皇冠844网站

javascript数组去重方法终极总结,js有序数组的连

1.前言 

有时会碰上这种需求,需要将数组中重复的元素删除掉,而只保留一个。最先想到的办法很可能就是用2个for循环来做比较然后去除掉重复的元素,代码如下所示:

昨天碰到一道关于如何解决有序数组的连接问题,这是一个很常见的问题。但是这里要考虑到代码的效率问题,因为要连接的数组都是有序的,这是一个非常重要的前提条件。

方法1:

2.简单但效率不高的算法 

复制代码 代码如下:

 我首先想到的是使用内置的concat方法,然后再对其进行排序,这种方法完全没有考虑到数组是有序的前提条件,代码如下:    

Array.prototype.distinct = function(){
 var arr = [],
      len = this.length;

复制代码 代码如下:

 for ( var i = 0; i < len; i ){
  for( var j = i 1; j < len; j ){
   if( this[i] === this[j] ){
    j = i;
   }
  }
  arr.push( this[i] );
 }
 return arr;
};

function concatSort(arrA,arrB){
     return arrA.concat(arrB).sort();
}

使用方法1如果碰到数据比较多时性能上会差很多。那么请继续看下面的方法。

  为了弄清楚sort排序到底使用的是什么算法,特地到看了V8引擎的算法(连接),大概意思是当数组的长度较短的时候使用的是插入排序(InsertionSort),当数组的长度较长的时候使用的是快速排序(QuickSort)。纠正了自己长时间来的一个误区,一直以为sort使用的是冒泡。

方法2:

  1. 取小值插入的方法 

复制代码 代码如下:

 大概思路:就是同时对两个数组进行遍历,设置两个标志(i,j)用于记录遍历的位置,将两个数组中较小的那个值插入新数组中,接着再将标志往前移动一个位置,重复比较,直到搜索值都插入到数组中。第一次做的时候判断条件写错了,所以出现了死循环,暴露了自己算法能力还是挺薄弱的。     

Array.prototype.distinct = function(){

复制代码 代码如下:

 var self = this,
  arr = self.concat().sort(); // 创建一个新数组并排序

function con(arrA,arrB){
   var i , j , k, lenA = arrA.length, lenB = arrB.length , allLen = lenA

 arr.sort(function( a, b ){
  if( a === b ){
   var n = self.indexOf( a ); //获取索引值
   self.splice( n, 1 );
  }
 });

  • lenB,result = [];
       for(i=0,j=0,k =0; k < allLen; k ){
           if(i < lenA &&(j >= lenB || arrA[i] < arrB[j])){
               result.push(arrA[i ]); 
           }else{
                result.push(arrB[j ]);
           }
       }
       return result;
    }
    var a = [1,2,4], b = [3,5,6,7,10];
    console.log(con(a,b));  //[1,2,3,4,5,6,7,10]

 return self;

  将这个算法与上面的方法1,在jsperf进行性能对比,发现第二种算法的效率明显优于第一种。不相信就猛击这里。

};

4.问题升级:增加合并数组的数量

方法2使用了 sort 的自定义回调函数,也用到了 indexOf 这个IE6/7/8不支持的方法。当然,indexOf可以自己模拟,但是更大的问题是IE6/7/8的sort方法和标准浏览器之间也有差别。在IE6/7/8中使用 sort 方法的自定义回调函数陷阱比较多,上面的自定义 sort 的回调函数的代码在IE6/7/8中会直接报“缺少数字”的错误,回调函数的返回是NaN的话就会报这个错,因为理论上 sort 的回调函数只能返回整数。就算忽略返回值的问题还是有其他问题,最后也没有过多的去纠结了,方法2在IE6/7/8中行不通。

  假如增加数组的个数,;例如 A = [1,5],B = [2,6],C = [3,4].......K = [....],求合并的数组。   

从愚人码头那里看来了方法3,下面是他的代码:

本文由澳门皇冠金沙网站发布于前端开发,转载请注明出处:javascript数组去重方法终极总结,js有序数组的连