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

数组去重

  •  
  •   wenjay · 184 天前 · 3947 次点击
    这是一个创建于 184 天前的主题,其中的信息可能已经有所发展或是发生改变。

    数组去重

     Array.prototype.unique1 = function () {
       var n = []; //一个新的临时数组
       for (var i = 0; i < this.length; i++) //遍历当前数组
       {
         if (n.indexOf(this[i]) == -1) n.push(this[i]);
       }
       return n
    }
    
    第 1 条附言  ·  184 天前
    面试老喜欢问这个
    征集下高级(装逼)回答,可以纵观发展历史、性能、工具又不太啰嗦。👻

    目前已知的高级回答:时间复杂度为 O(n^2),空间复杂度为 O(n)😂
    49 回复  |  直到 2019-07-23 09:13:03 +08:00
    zhao7399686
        1
    zhao7399686   184 天前
    ?
    NewDraw
        2
    NewDraw   184 天前 via Android
    这代码是在养蛊啊!
    AlloVince
        3
    AlloVince   184 天前   ♥ 5
    ``` js
    Array.from(new Set(inputArray));
    ```
    wenjay
        4
    wenjay   184 天前
    发出去的文章不能修改的吗?
    wunonglin
        5
    wunonglin   184 天前
    wenjay
        6
    wenjay   184 天前
    @AlloVince ES6 就是如此简单,不过面试老喜欢问这个问题,要如何回答才能显得高级呢😂
    Yumwey
        7
    Yumwey   184 天前
    用 filter 一行就写完了
    starsriver
        8
    starsriver   184 天前 via Android
    es6 new 的 array 自动去重。
    wenjay
        9
    wenjay   184 天前
    lihongjie0209
        10
    lihongjie0209   184 天前
    数据结构没学好?
    xingyue
        11
    xingyue   184 天前
    我这是要完犊子了吗,看了半天没觉得有什么问题.....除了代码啰嗦了点。再看看 #1 #2 #10,现在内心慌的一.....
    taogen
        12
    taogen   184 天前 via Android
    就说算法的时间复杂度为 O(n^2),空间复杂度为 O(n)。高级否?
    taogen
        13
    taogen   184 天前 via Android
    另外,用 hash table 作为中间容器,时间复杂度可以为 O(n)
    oIMOo
        14
    oIMOo   184 天前
    转成 set 再转回 list 怎么样?
    lynnic
        15
    lynnic   184 天前 via Android
    时间复杂度为啥是 n 方?
    necomancer
        16
    necomancer   184 天前
    @lynnic indexof 是 o(n) 的吧
    kyuuseiryuu
        17
    kyuuseiryuu   184 天前 via iPhone
    @necomancer 外面还有一层 n🤣
    serenader
        18
    serenader   184 天前   ♥ 2
    LZ 的这个方法有个 bug,无法去重 NaN 以及 {} 。

    几年前我写过一篇文章,也是讲去重的:blog.serenader.me/javascript-shu-zu-qu-zhong/

    不过刚刚看了一下,我文章里面最后给出的方案也有 bug。。纯粹当抛砖引玉了,看看大家能找到几个 bug 🤣🤣
    indomi
        19
    indomi   184 天前
    [...new Set(arr)]
    bumz
        20
    bumz   184 天前 via iPhone
    ES6 之前就手写一哈希表,高级吗,手动狗头
    15651980765
        21
    15651980765   184 天前
    @Yumwey 请问用 filter 是这样吗?
    Array.prototype.unique = function() {
    return this.filter(function(item, index, array) {return array.indexOf(item) === index});
    }
    我测了一下这种方法在数组很长( 4000w+)的情况下,耗时差不多是楼主方法的两倍。
    Array.from(new Set(array))这种比楼主的方法稍微快一点
    stillsilly
        22
    stillsilly   184 天前
    let a = [1,1,2,2,2,3,3]
    let b = [...new Set(a)]
    console.log(b)
    imbacc
        23
    imbacc   184 天前
    后排吃瓜
    karllynn
        24
    karllynn   184 天前
    用 hash 的话,数组的顺序会变的…楼主这个时间复杂度太高了
    QiaTia
        25
    QiaTia   184 天前
    ```
    Array.prototype.unique1 = function () {
    var n = {}; //一个新的临时数组
    for (var i = 0; i < this.length; i++) //遍历当前数组
    {
    if (n.[this[i]] !== 'a') n[this[i]]='a'
    }
    return Object.keys(n)
    }
    ```
    QiaTia
        26
    QiaTia   184 天前
    @QiaTia 多打了一个点 if (n[this[i]] !== 'a')
    dartabe
        27
    dartabe   184 天前
    之前在写 leetcode 的时候用的 set 做的中间容器. 时间复杂度 O(n)

    后来发现 set 自动就可以去重了
    dartabe
        28
    dartabe   184 天前
    不过 javascript 对象直接就是哈希表了? 用 set 的话我只是懒得存 1/0 或者 true /false

    求大佬看我理解对不对
    weixiangzhe
        29
    weixiangzhe   184 天前 via iPhone
    这种东西 直接看 lodash 源码最靠谱了
    reus
        30
    reus   184 天前
    把 indexOf 改成对 Set 的操作,用 Set 辅助去重
    如果没有 Set,那就自己实现一个
    CodingNaux
        31
    CodingNaux   184 天前 via iPhone
    unique ( collection,func)
    RoshanWu
        33
    RoshanWu   184 天前
    wozhizui
        34
    wozhizui   184 天前
    @oIMOo 俺也一样
    Arizas
        35
    Arizas   184 天前
    uniqueResult = [...new Set(arr)]
    Aoerz
        36
    Aoerz   184 天前 via Android
    首先排序,然后遍历,时间复杂度 O(n),空间复杂度 O(1)
    Snail233
        37
    Snail233   184 天前
    es6 不是有 set 么、
    lihongjie0209
        38
    lihongjie0209   184 天前   ♥ 3
    @Aoerz
    排序的 nlogn 的时间复杂度不算了?
    Fairy1128
        39
    Fairy1128   184 天前
    难道不是先问 数组的 item 是普通类型还是引用类型吗
    Laumm
        40
    Laumm   183 天前
    @Aoerz 既然都需要排序了,时间复杂度就应该大于 O(n)
    Laumm
        41
    Laumm   183 天前
    感觉最简单就是放 Set 里了
    arnoldxiao
        42
    arnoldxiao   183 天前
    用 Set 含一下再放回去
    fengdechoulian
        43
    fengdechoulian   183 天前
    @arnoldxiao 仰望高端玩家
    doing1
        44
    doing1   183 天前
    我服了
    Aoerz
        45
    Aoerz   183 天前 via Android
    @Laumm 是的,把排序这茬给忘了
    DRcoding
        46
    DRcoding   183 天前
    所谓的 filter
    var r = ['aa','bb','cc','bb'].filter(function (ele, index, self) {
    return self.indexOf(ele) === index;
    });
    console.log(r.toString());
    ChiangDi
        47
    ChiangDi   183 天前 via iPhone
    不能先排序吧,数组里可能有数字可能有字符串或者其它任何东西
    YouMoeYi
        48
    YouMoeYi   183 天前
    为啥不用 Set
    function arr_dr (arr){
    let st = new Set(arr);
    return [...st];
    }
    mystorp
        49
    mystorp   180 天前
    Array.prototype.unique1 = function () {
    let m = new Map;
    for (var i = 0; i < this.length; i++) //遍历当前数组
    {
    // 不同于 {}, Map 是有序的哈希表
    // Map 的 key 可以是任意 js 值
    m.set(this[i], true);
    }
    return m.keys();
    }

    let arr = [1, 1, 2, 2, NaN, NaN, null, null, undefined, undefined, {}, [], Symbol.split, '', '', false, false];
    console.log(arr.unique1());
    // MapIterator { 1, 2, NaN, null, undefined, {}, [], Symbol(Symbol.split), '', false }
    arr.push(arr.shift(), arr.shift());
    console.log(arr.unique1());
    // MapIterator { 2, NaN, null, undefined, {}, [], Symbol(Symbol.split), '', false, 1 }
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4175 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 43ms · UTC 08:01 · PVG 16:01 · LAX 00:01 · JFK 03:01
    ♥ Do have faith in what you're doing.