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 · 2019-07-18 20:19:56 +08:00 · 6598 次点击
    这是一个创建于 1953 天前的主题,其中的信息可能已经有所发展或是发生改变。

    数组去重

     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 条附言  ·  2019-07-18 21:58:02 +08:00
    面试老喜欢问这个
    征集下高级(装逼)回答,可以纵观发展历史、性能、工具又不太啰嗦。👻

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

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

    不过刚刚看了一下,我文章里面最后给出的方案也有 bug。。纯粹当抛砖引玉了,看看大家能找到几个 bug 🤣🤣
    indomi
        19
    indomi  
       2019-07-19 00:26:16 +08:00
    [...new Set(arr)]
    bumz
        20
    bumz  
       2019-07-19 09:15:41 +08:00 via iPhone
    ES6 之前就手写一哈希表,高级吗,手动狗头
    15651980765
        21
    15651980765  
       2019-07-19 10:04:19 +08:00
    @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  
       2019-07-19 10:11:15 +08:00
    let a = [1,1,2,2,2,3,3]
    let b = [...new Set(a)]
    console.log(b)
    imbacc
        23
    imbacc  
       2019-07-19 10:13:57 +08:00
    后排吃瓜
    karllynn
        24
    karllynn  
       2019-07-19 10:48:11 +08:00
    用 hash 的话,数组的顺序会变的…楼主这个时间复杂度太高了
    QiaTia
        25
    QiaTia  
       2019-07-19 11:18:13 +08:00
    ```
    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  
       2019-07-19 11:18:45 +08:00
    @QiaTia 多打了一个点 if (n[this[i]] !== 'a')
    dartabe
        27
    dartabe  
       2019-07-19 11:45:12 +08:00
    之前在写 leetcode 的时候用的 set 做的中间容器. 时间复杂度 O(n)

    后来发现 set 自动就可以去重了
    dartabe
        28
    dartabe  
       2019-07-19 12:07:08 +08:00
    不过 javascript 对象直接就是哈希表了? 用 set 的话我只是懒得存 1/0 或者 true /false

    求大佬看我理解对不对
    weixiangzhe
        29
    weixiangzhe  
       2019-07-19 12:16:26 +08:00 via iPhone
    这种东西 直接看 lodash 源码最靠谱了
    reus
        30
    reus  
       2019-07-19 12:21:23 +08:00
    把 indexOf 改成对 Set 的操作,用 Set 辅助去重
    如果没有 Set,那就自己实现一个
    CodingNaux
        31
    CodingNaux  
       2019-07-19 12:22:40 +08:00 via iPhone
    unique ( collection,func)
    wozhizui
        34
    wozhizui  
       2019-07-19 12:27:56 +08:00
    @oIMOo 俺也一样
    Arizas
        35
    Arizas  
       2019-07-19 12:34:18 +08:00
    uniqueResult = [...new Set(arr)]
    Aoerz
        36
    Aoerz  
       2019-07-19 13:32:55 +08:00 via Android
    首先排序,然后遍历,时间复杂度 O(n),空间复杂度 O(1)
    Snail233
        37
    Snail233  
       2019-07-19 13:39:56 +08:00
    es6 不是有 set 么、
    lihongjie0209
        38
    lihongjie0209  
       2019-07-19 13:44:05 +08:00   ❤️ 3
    @Aoerz
    排序的 nlogn 的时间复杂度不算了?
    Fairy1128
        39
    Fairy1128  
       2019-07-19 14:56:46 +08:00
    难道不是先问 数组的 item 是普通类型还是引用类型吗
    Laumm
        40
    Laumm  
       2019-07-19 16:04:13 +08:00
    @Aoerz 既然都需要排序了,时间复杂度就应该大于 O(n)
    Laumm
        41
    Laumm  
       2019-07-19 16:04:39 +08:00
    感觉最简单就是放 Set 里了
    arnoldxiao
        42
    arnoldxiao  
       2019-07-19 16:14:21 +08:00
    用 Set 含一下再放回去
    fengdechoulian
        43
    fengdechoulian  
       2019-07-19 16:22:34 +08:00
    @arnoldxiao 仰望高端玩家
    doing1
        44
    doing1  
       2019-07-19 16:45:37 +08:00
    我服了
    Aoerz
        45
    Aoerz  
       2019-07-19 17:00:07 +08:00 via Android
    @Laumm 是的,把排序这茬给忘了
    DRcoding
        46
    DRcoding  
       2019-07-19 18:19:12 +08:00
    所谓的 filter
    var r = ['aa','bb','cc','bb'].filter(function (ele, index, self) {
    return self.indexOf(ele) === index;
    });
    console.log(r.toString());
    ChiangDi
        47
    ChiangDi  
       2019-07-19 18:30:20 +08:00 via iPhone
    不能先排序吧,数组里可能有数字可能有字符串或者其它任何东西
    YouMoeYi
        48
    YouMoeYi  
       2019-07-19 18:50:31 +08:00
    为啥不用 Set
    function arr_dr (arr){
    let st = new Set(arr);
    return [...st];
    }
    mystorp
        49
    mystorp  
       2019-07-23 09:13:03 +08:00
    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 }
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5656 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 43ms · UTC 06:08 · PVG 14:08 · LAX 22:08 · JFK 01:08
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.