V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
codespots
V2EX  ›  JavaScript

JavaScript 算法初探——数组去重

  •  
  •   codespots · 2016-03-07 16:50:43 +08:00 · 5794 次点击
    这是一个创建于 2943 天前的主题,其中的信息可能已经有所发展或是发生改变。

    本文原发布在 segmentfault.com https://segmentfault.com/a/1190000004548931 在学是作者,现在贴到 V2EX ,所以不存在侵权。

    前言

    最近为了换工作,准备下面试,开始回顾复习 JavaScript 相关的知识,昨天下午想到了数组去重的相关方法,干脆整理出几篇 JavaScript 算法文章,以备后用,此系列文章不定篇数,不定时间,想到哪写到哪,不保证正确性,不保证高效率,只是谈谈个人理解,如有错误,请诸位斧正。

    关于去重

    数组去重是一个比较常见的算法考察点,实现去重的方式无外乎通过唯一性和非唯一性。简单来讲就是挑出唯一的或者删除不唯一的。以下所有算法都是我自己瞎命名的,请无视之。

    循环匹配去重

    顾名思义,就是把数组中的每一个元素都和存放元素的数组对比,遇到不重复的元素,放入新数组中,直至循环结束,由于匹配也有循环,也可以称为双循环匹配去重,这也是大家都能想到的最简单的方式。

    实现代码:

    var arr=[1,3,4,56,3,7,9,7];
    var result=[];
    //匹配
    function isMatch(array,n){
        for(var i=0;i<array.length;i++){
            if(array[i]==n){
                return true;
            }
        }
        return false;
    };
    //验证所有元素
    function unqiue(array){
        for(var i=0;i<array.length;i++){
            if(!isMatch(result,array[i])){
                result.push(array[i]);
            }
        }
        return result;
    };
    
    console.log(unqiue(arr));
    
    注意:上面方法有一个 bug ,当存在数字和数字形式的字符串的时候,没有区分出数字和数字字符串。因为在匹配函数 isMatch()里用的是双等“==”,没有验证元素类型,实际应该使用全等“===”。
    

    修改后的代码如下:

    var arr=[1,3,4,56,3,'1',7,9,7];
    var result=[];
    //匹配
    function isMatch(array,n){
        for(var i=0;i<array.length;i++){
            if(array[i]===n){
                return true;
            }
        }
        return false;
    };
    //验证所有元素
    function unqiue(array){
        for(var i=0;i<array.length;i++){
            if(!isMatch(result,array[i])){
                result.push(array[i]);
            }
        }
        return result;
    };
    
    console.log(unqiue(arr));
    

    算法优缺点:

    优点:

    1. 实现简单,思路直观

    缺点:

    1. 效率低下

    JSON 去重 /对象去重 /字典去重 1

    JSON 去重,简单来讲就是利用 Object 对象 key 的唯一性,将数组的元素转换为 JSON 或者说对象的 key 值。 JSON 的 value 存储数组的索引 index ,然后对 JSON 对象进行 for in 循环,存储到新数组中。

    Array 、 JSON 、{}都是 Object ,所以采用任意一种都可以实现此算法。

    实现代码:

    Array 方式:

    var arr=[1,3,4,56,3,'1',7,9,7];
    function unqiue(array){
        var cache=[];
        var result=[];
         //将数组元素转为对象的 key
        for(var i=0;i<array.length;i++){
            cache[array[i]]=i;
        };
    
        //存储 key(实际的数组元素)
        for(key in cache){
            result.push(key);
        };
    
        return result;
    }
    
    console.log(unqiue(arr));
    

    JSON 方式:
    ```
    var arr=[1,3,4,56,3,'1',7,9,7];
    function unqiue(array){
    var cache={};
    var result=[];
    //将数组元素转为对象的 key
    for(var i=0;i<array.length;i++){
    cache[array[i]]=i;
    };

    //存储 key(实际的数组元素)
    for(key in cache){
        result.push(key);
    };
    
    return result;
    

    }

    console.log(unqiue(arr));
    ```

    Object 方式:

    var arr=[1,3,4,56,3,'1',7,9,7];
    function unqiue(array){
        var cache=new Object();
        var result=[];
         //将数组元素转为对象的 key
        for(var i=0;i<array.length;i++){
            cache[array[i]]=i;
        };
    
        //存储 key(实际的数组元素)
        for(key in cache){
            result.push(key);
        };
    
        return result;
    }
    
    console.log(unqiue(arr));
    

    算法优缺点:

    优点:

    1. 简单
    2. 效率非常高

    缺点:

    1.改变了数组元素的类型(去重后的元素都为字符串类型)
    2.无法区分数字和数值型字符串

    JSON 去重 /对象去重 /字典去重 2

    第 2 种方式和第 1 种方式在本质上没有太多区别,反而因为做了判断,效率降低了一点点。

    实现代码

    var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];
    function unqiue(array){
        var cache={};
        var result=[];
        for(var i=0;i<array.length;i++){
            //如果 json 或者是或 hash 里没有
            if(!cache[array[i]]){
                result.push(array[i]);
                //设置当前结果为已存在
                cache[array[i]]=true;
            }
        }
        return result;
    }
    
    console.log(unqiue(arr));
    

    为什么说第 2 种方式和第一种方式没有本质的区别呢?第 2 种方式有一个临时的 hash 表 cache ,存储了最终结果 result 中是否存在对应元素记录。如果 cache 中的记录不存在,说明该数组元素没有重复。第 1 种方式没有做判断,因为 json 数组,对象等,本质就可以看做是 hash , cache[array[i]]中 array[i]相同的只会存在一个,所以不需要做判断。这也是第 1 种更快一点点的原因,虽然效率没有第 1 种那么高,但这种方式引入了一种解决第 1 种方式 bug 的潜在方案,在为 Array 添加去重方式的时候会提到这个方案。

    算法优缺点:

    优点:

    1. 效率很高

    缺点:

    1. 无法区分数字和数值型字符串

    队尾递归去重

    昨天晚上思忖良久想到用队列的方式,先将数组排序成升序或降序的队列,这样相同的元素就处在一个区域内,然后从队尾向前匹配,如果匹配成功,删除队尾,然后前一个元素再向其前面的匹配。整个匹配完成之后,剩下的元素就是去重过后的队列。

    var arr=[6, 4, 6, 9, '6', 13, 56, 9, ,'11',1, 8, '7', 17, 5, 45, 3, 7];
    
    function unqiue(array){
        //排序数组,形成队列
        array.sort(function(m,n){return m-n;});
        ////排序后,队尾向前对比,如果相同,删除队尾,依次类推
        function loop(Index){
            if(Index>=1){
                if(array[Index]===array[Index-1]){
                    arr.splice(Index,1);
                }
                loop(Index-1);
            }
    
        }
        loop(array.length-1);
        return array;
    }
    
    console.log(unqiue(arr));
    

    算法优缺点:

    优点:

    1. 效率较高

    缺点:

    1. 没有保留原数组的顺序

    indexOf 去重 1

    ECMAScript5 为数组添加了两个位置方法: indexOf()和 lastIndexOf()。如果查找不到相应的数组元素,返回-1 。所以可以使用 indexOf 方式来去重。

    实现代码:

    var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];
    
    function unqiue(array){
        var result=[];
        for(var i=0;i<array.length;i++){
            if(result.indexOf(array[i])==-1){
                result.push(array[i]);
            }
        }
    
        return result;
    }
    
    console.log(unqiue(arr));
    

    优点:

    1. 效率较高

    缺点:
    2. 不兼容低版本浏览器( ECMAScript5 才支持 indexOf()和 lastIndexOf()方法)

    indexOf 去重 2

    从上面的 indexOf 去重扩展开来,如果用 indexOf 查找一个数组的元素的结果不是该数组元素的索引,那么可以认为这个数组出现过。所以这也可以用来实现数组去重。

    var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];
    
    function unqiue(array){
        var result=[];
        for(var i=0;i<array.length;i++){
            if(array.indexOf(array[i])==i){
                result.push(array[i]);
            }
        }
    
        return result;
    }
    
    console.log(unqiue(arr));
    

    其实循环判断可以从第 1 项开始,因为第 0 项肯定不会重复。

    优点:

    1. 效率较高

    缺点:
    2. 不兼容低版本浏览器( ECMAScript5 才支持 indexOf()和 lastIndexOf()方法)

    为 Array 对象添加去重方法的坑

    以上总结了几种去重方法,我们来个小例子为 Array 对象添加去重,方便直接调用,实际情况下我们是不推荐修改 JavaScript 原生对象的,容易造成污染或者不可控的情况的发生。

    以 JSON 去重 1 的方式为 Array 添加对象,我们选用了“ cache=[]”的那种,结果不小心踩到了大坑。
    ```
    var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];

    Array.prototype.unqiue=function(){
    var cache=[];
    var result=[];
    for(var i=0;i<this.length;i++){
    cache[this[i]]=i;
    }

    for(key in cache){
        result[cache[key]]=key;
    }
    
    return result;
    

    }

    console.log(arr.unqiue());
    ```

    图片描述

    结果居然把 Array 本身的 unqiue 方法也当做数组的内容输出出来了。

    再对比下使用 JSON 或者对象的方式的结果
    ```
    var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];

    Array.prototype.unqiue=function(){
    var cache={};
    var result=[];
    for(var i=0;i<this.length;i++){
    cache[this[i]]=i;
    }

    for(key in cache){
        result[cache[key]]=key;
    }
    
    return result;
    

    }
    console.log(arr.unqiue());
    ```
    图片描述

    结果是正常的。

    所以,我们在向 Array 对象添加去重方法时,不能使用[]的方式,要使用 JSON 或者空对象的方式,但是依然无法区分数值和数值型字符串。

    JSON 去重 3

    在 JSON 去重 2 我们判断的是 cache[array[i]]值是否为真。 cache[array[i]]这种实际是当做 cache 的自定义属性存储的, array[i]被转成了字符串形式,也同样存在无非区分数值和数值型字符串的情况,所以我们需要对 JSON 方式 2 进行改造。

    代码如下:

    var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];
    function unqiue(array){
        var cache={};
        var result=[];
        for(var i=0;i<array.length;i++){
            var record=typeof(array[i])+array[i];
            //如果 json 或者是或 hash 里没有
            if(!cache[record]){
                result.push(array[i]);
                //设置当前结果为已存在
                cache[record]=true;
            }
        }
        return result;
    }
    
    console.log(unqiue(arr));
    

    相比于 JSON 去重 2 ,我们对判断条件做了修改, cache[array[i]]存在数值和数值字符串时[array[i]]相同的情况,但是[typeof(array[i])+array[i]]却不存在这种情况,数值的 typeof 为 number ,数值字符串的 typeof 为 string ,区分开了这两种情况。

    所以最终我们为 Array 对象添加的是这样的去重方法

    var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];
    Array.prototype.unqiue=function(){
        var cache={};
        var result=[];
        for(var i=0;i<this.length;i++){
            var record=typeof(this[i])+this[i];
            //如果 json 或者是或 hash 里没有
            if(!cache[record]){
                result.push(this[i]);
                //设置当前结果为已存在
                cache[record]=true;
            }
        }
        return result;
    }
    
    
    console.log(arr.unqiue());
    

    补充队列去重方式

    从网友哪里知道另外的两种队列方式,代码如下,原理和我写的队尾递归去重类似,代码如下:

    队尾去重

    var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];
    function unqiue(array){
        var result=[];
        array.sort(function(m,n){return m-n});
        for(var i=0;i<array.length;i++){
            if(array[i]!==result[result.length-1]){
                result.push(array[i]);
            }
        }
    
        return result;
    }
    
     console.log(unqiue(arr));
    

    队首去重

    var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];
     function unqiue(array){
        var result=[];
        array.sort(function(m,n){return n-m});
        for(var i=0;i<array.length;i++){
            if(array[i]!==result[0]){
                result.unshift(array[i]);
            }
        }
    
        return result;
    
     }
     console.log(unqiue(arr));
    

    附言:

    关于 JavaScript 数组去重的方式基本就总结到这里了,欢迎在评论里指出错误和贡献其他方法。

    34 条回复    2016-03-08 16:00:11 +08:00
    otakustay
        1
    otakustay  
       2016-03-07 17:16:19 +08:00   ❤️ 1
    咱们直接用 Map 类就好了嘛……
    sumhat
        2
    sumhat  
       2016-03-07 17:20:14 +08:00 via iPhone
    谈到算法效率的时候,请给出时空复杂度。
    xqin
        3
    xqin  
       2016-03-07 17:25:41 +08:00   ❤️ 1
    我想说的是: 楼主居然分不清 `JSON` 和 `Object`, 以及居然不知道 `{}` 是 `new Object` 的缩写.
    居然单独把 var cache = {} 做为 `JSON` 拿来讲.
    markowitz73
        4
    markowitz73  
       2016-03-07 17:34:21 +08:00
    如果不保证效率,那么算法有什么意义呢?
    holyghost
        5
    holyghost  
       2016-03-07 17:37:25 +08:00
    咱们直接用 Set 类就好了嘛……
    ChiChou
        6
    ChiChou  
       2016-03-07 17:46:22 +08:00
    我也想吐槽 JSON 这个说法
    sampeng
        7
    sampeng  
       2016-03-07 17:55:29 +08:00
    特意来登陆吐槽 JSON 的。。
    用同样的时间做去重,用 map ,只是消耗现代机器无视的内存占用来去重。可以最少比你多写 3 个函数了。。。
    jsonline
        8
    jsonline  
       2016-03-07 18:03:54 +08:00 via Android
    JSON 是哪四个单词的全称楼主
    learnshare
        9
    learnshare  
       2016-03-07 18:08:05 +08:00
    JSON 是文件格式 /文本格式吧

    `!cache[array[i]]` 不能用来判断 `value == false` 的情况
    daysv
        10
    daysv  
       2016-03-07 18:11:12 +08:00
    [ 1, 1, 'a', 'a' ].filter( (el, i, arr) => arr.indexOf(el) === i);

    Array.from( new Set([ 1, 1, 'a', 'a' ]) );

    一般这样就好了吧,搞的长篇大论啊??
    codespots
        11
    codespots  
    OP
       2016-03-07 18:30:07 +08:00
    统一回复下 JSON 的问题,这个确实是我失误没有说清楚,本来只是用比较通俗的说法来解释下{}去重的方式,本来想用字典吧,但是字典属于 python 的说法。所以就用了 json 来指代下,因为 json 的 key 也具有唯一性嘛,给各位道歉,至于{}和 new object 缩写我是知道的,以后不敢随便在 V2EX 上发文章了,太可怕了。
    codespots
        12
    codespots  
    OP
       2016-03-07 18:31:40 +08:00
    至于为什么不用 object 来指代,因为 json 格式比较易于理解,也容易让各位注意到实际上数组元素的类型已经被转换为了字符串,考虑不周,还望见谅。
    codespots
        13
    codespots  
    OP
       2016-03-07 18:38:16 +08:00
    @learnshare !cache[array[i]] 可以判断 value==false 的情况,这里的 false 只是做了新对象的 key ,实际是!cache[“ false ”]

    @jsonline @sampeng @ChiChou @xqin JSON 是 JavaScript Object Notation 的缩写,抱歉啊,才疏学浅,表达不严谨,出了问题,请各位见谅。另外请教各位, V2EX 的帖子怎么删除啊,不敢再误导其他人。吾长见笑于大方之家
    zhujinliang
        14
    zhujinliang  
       2016-03-07 19:00:07 +08:00 via iPhone
    不先 sort 然后依次比对么?
    v1024
        15
    v1024  
       2016-03-07 19:05:43 +08:00
    [...new Set([1, 1, 2, 2, 3, "a", "a"])]

    搞定。。
    sagnitude
        16
    sagnitude  
       2016-03-07 19:16:37 +08:00
    for-in 很慢,数量级级别的慢(除了 IE ),不要用 for-in
    jianzong
        17
    jianzong  
       2016-03-07 19:26:05 +08:00
    算法在哪?
    bumz
        18
    bumz  
       2016-03-07 19:32:44 +08:00 via iPhone
    ES6:
    Array.from(new Set(array).values())
    yoa1q7y
        19
    yoa1q7y  
       2016-03-07 19:50:56 +08:00
    @westooy 这里都是大神,没把握最好不要发文章 (逃
    pupboss
        20
    pupboss  
       2016-03-07 20:52:17 +08:00
    为什么 indexOf 的效率高,求证明,不是找茬
    因为我只能想到这一种办法去重了
    一直觉得效率很低下
    codespots
        21
    codespots  
    OP
       2016-03-07 21:07:08 +08:00
    @pupboss 是相对高,不是最高,最高是字典去重,用空间换时间, ES6 原生的方式我没测过
    murmur
        22
    murmur  
       2016-03-07 21:20:01 +08:00
    map 背后的实现应该是 hashmap 吧?
    trotyl
        23
    trotyl  
       2016-03-07 21:26:58 +08:00
    @westooy 说的好像 indexOf 不是循环一样。。
    jarnanchen
        24
    jarnanchen  
       2016-03-07 21:43:19 +08:00
    @daysv 说的方法就很好了啊
    xuwenmang
        25
    xuwenmang  
       2016-03-07 21:45:54 +08:00
    @westooy 别跟网友计较,网友是什么,你说 xx 地方地政了,他们有一堆在下面讨论错别字的。

    另外别发表文章到这里,发个链接就行了。这里不适合。没有销户,删除的地方,不要发文章。
    WittBulter
        26
    WittBulter  
       2016-03-08 04:04:44 +08:00
    目前只有 Set 是 O(n)吧...
    keyanzhang
        27
    keyanzhang  
       2016-03-08 08:56:42 +08:00
    const nums = [ 1, 2, 1, 3, 1, 2, 4 ];

    const withoutDups = Array.from(new Set(nums));
    vagary
        28
    vagary  
       2016-03-08 09:09:47 +08:00
    @zhujinliang 鱼爆一地
    xunuoi
        29
    xunuoi  
       2016-03-08 09:46:54 +08:00
    调用数组自己的 sort 方法后再做队列排序, sort 本身已经增加了复杂度了,整体效率并不会高
    xqin
        30
    xqin  
       2016-03-08 11:00:14 +08:00
    @xuwenmang 这话你说的就不对了, 他不发出来, 他怎么知道自己的不足?
    你为什么看到的只是别人在挑他的毛病?
    别人能找出来原因, 这只能说明他做的还不够, 自己还有不足的地方,
    还需要学习. 这是在帮助他进步 好不好?
    @westooy
    codespots
        31
    codespots  
    OP
       2016-03-08 11:14:05 +08:00
    感谢各位,我确实有很多不足,谢谢各位,我会努力的,年轻人还是要提高自己的姿势水平!
    Jaylee
        32
    Jaylee  
       2016-03-08 11:44:17 +08:00
    23333 年轻人还是要多提高自己的姿势水平再来写文章啊
    neoblackcap
        33
    neoblackcap  
       2016-03-08 15:54:22 +08:00
    文章其实还好,但是觉得没有深入到根基,其实去重算法我觉得基本上就是基于 hash 的,还有神奇的 bloom-filter,当然也有简单暴力算法。
    还有就是改变数据类型这个我觉得不是事吧,你在暴露的接口那里,再转换回去就好了嘛。你算法内部的数据结构怎么会是一个问题呢?关键是你要给出对应的时空复杂度,那才有讨论算法的价值。
    tedzhou
        34
    tedzhou  
       2016-03-08 16:00:11 +08:00
    就问一句 indexOf 的时间复杂度是多少?
    还有 lz 列的 n 种写法其实是等效的。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3437 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 00:45 · PVG 08:45 · LAX 17:45 · JFK 20:45
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.