首页 > 程序开发 > web前端 > HTML/CSS >

数组去重

2017-03-18

数组去重:总结下数组去重的四种常见的做法,以及相应的运行时间的比较:方法1: 创建一个新的临时数组来保存数组中已有的元素。

数组去重:总结下数组去重的四种常见的做法,以及相应的运行时间的比较:方法1: 创建一个新的临时数组来保存数组中已有的元素。

Array.prototype.unique1 = function(){
    var n = [];     //一个新的临时数组
    for(var i=0; i

方法2. 使用哈希表存储已有的元素

Array.prototype.unique2 = function(){
    var hash = {},
        n = [];     //hash 作为哈希表, n为临时数组
    for(var i=0; i

方法3. 使用indexOf判断数组元素第一次出现的位置是否为当前位置

Array.prototype.unique3 = function(){
    var n = [this[0]]; 
    for(var i=1; i

方法4. 先排序再去重

Array.prototype.unique4 = function(){
    this.sort(function(a, b){ return a - b;});
    var n = [this[0]];
    for(var i=1; i

第一种方法和第三种方法都使用了indexOf(), 这个函数的执行机制也会遍历数组 第二种方法使用了一个哈希表, 是最快的. 第三种方法也有一个排序的复杂度的计算.

然后做了个测试, 随机生成10000个0-10000的数组结果如下:

  function randomFn(){
        return Math.floor(Math.random()*10000);
    }

    var a=[];
    for(var i=0;i<10000;i++){
        a.push(randomFn());
    }

    var begin1 = new Date();
    a.unique1();
    var end1 = new Date();

    var begin2 = new Date();
    a.unique2();
    var end2 = new Date();

    var begin3 = new Date();
    a.unique3();
    var end3 = new Date();

    var begin4 = new Date();
    a.unique4();
    var end4 = new Date();

    console.log("方法一执行时间:" + (end1 - begin1));
    console.log("方法二执行时间:" + (end2 - begin2));
    console.log("方法三执行时间:" + (end3 - begin3));
    console.log("方法四执行时间:" + (end4 - begin4));

结果如下:

由此可见,第二种算法时间最快,以空间换时间。

相关文章
最新文章
热点推荐