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

昨天面试,今天发现面试官 2 个问题都弄错了

  •  
  •   lazyzml · 2018-05-31 22:35:11 +08:00 · 6935 次点击
    这是一个创建于 2350 天前的主题,其中的信息可能已经有所发展或是发生改变。

    首先第一个问题是\w 匹配什么,我说的匹配小写 a-z,然后他说不对,是匹配空格,tab 符那些。

    然后第二个问题是 js 如何数组去重

    我回答第一个方法是 new Set(arr)去重,第二个方法是通过递归然后比较。我主要考虑到了对象。 面试官大意是何必用递归那么复杂的,直接再建一个数组,然后 indexOf 判断。我当时想,哎,没想到用 indexOf 判断,现在想来,indexOf 并不能比较对象,面试官说错了。

    38 条回复    2018-06-09 15:51:31 +08:00
    fulvaz
        1
    fulvaz  
       2018-05-31 22:40:21 +08:00
    肯定是数组去重呀, 对象就没重的啊?
    lazyzml
        2
    lazyzml  
    OP
       2018-05-31 22:42:08 +08:00
    @fulvaz 就是数组去重,不过数组里面可能包含对象啊。
    Via8veritas
        3
    Via8veritas  
       2018-05-31 22:42:33 +08:00
    好像\w 数字也可以?
    不过这样的公司没进去是好事吧。
    uxstone
        4
    uxstone  
       2018-05-31 22:44:38 +08:00
    lodash _.uniq()
    yangqi
        5
    yangqi  
       2018-05-31 22:45:56 +08:00
    \w 你说的也不对,匹配的是 word, 等同于[A-Za-z0-9_]
    lazyzml
        6
    lazyzml  
    OP
       2018-05-31 22:47:17 +08:00
    @yangqi 确实,我也没说对。
    yangqi
        7
    yangqi  
       2018-05-31 22:47:24 +08:00
    如果是大写的\W, 那就是 not word, 就是那些符号啥的,你确定你大小写没看错?
    xy90321
        8
    xy90321  
       2018-05-31 22:47:31 +08:00
    你首先得搞清楚是 \w 还是 \W 然后再讨论...

    你们俩说的都不是一个东西那当然没得谈了
    ryd994
        9
    ryd994  
       2018-05-31 23:28:43 +08:00 via Android
    新建一个数组然后插入前 indexof 吧
    从计算复杂度上来讲和递归一样 O(n^2)
    空间复杂读上来讲还不够好

    好的办法:
    两个指针,一个指向读的位置,一个指向写的位置
    写之前扫描 [0,写],有重复就 pass
    O(1)空间

    计算复杂度最低应该就是 Set O(nlogn)

    递归确实难维护一点,所以文档要写清楚递归的设计,比如不变式,终止条件。而且递归一定可以用循环实现。能转成尾递归的,就可以转成很简单的循环。所以递归不推荐用。
    但是要说“递归那么复杂的”,呵呵呵。
    earendil1412
        10
    earendil1412  
       2018-05-31 23:34:30 +08:00 via Android
    第二题的面试官答案要笑死我,空间 On 时间 On^2,能不能更牛逼一点,来个猴子去重我看不错
    fulvaz
        11
    fulvaz  
       2018-05-31 23:35:37 +08:00
    @lazyzml 即使是对象也能 indexOf 啊. 而且也不需要递归.

    ````
    arr.reduce((p, n) => {
    return p.indexOf(n) === -1 ? [...p, n] : p;
    }, [])
    ````

    你看, 不用递归

    (话说 indexOf 的复杂度是啥?)
    lazyzml
        12
    lazyzml  
    OP
       2018-05-31 23:49:44 +08:00
    @fulvaz 是我没用对吗?还是没成功去重。
    [截图]( )
    Chingim
        13
    Chingim  
       2018-05-31 23:52:25 +08:00 via Android
    @fulvaz 楼主的意思是 indexOf 不能比较两个值相等的对象
    rabbbit
        14
    rabbbit  
       2018-05-31 23:56:53 +08:00
    不可以比较对象吗?
    lazyzml
        15
    lazyzml  
    OP
       2018-06-01 00:04:06 +08:00
    @rabbbit 你这个 a 指向同一个内存地址了。。。所以 indexOf 不会返回-1
    autoxbc
        16
    autoxbc  
       2018-06-01 00:05:16 +08:00
    一般去重的说法,不把序列化一致看做重复值;何况 new Set(arr) 也无法判断序列化一致,所以楼主两种方法是矛盾的
    rabbbit
        17
    rabbbit  
       2018-06-01 00:09:17 +08:00
    @lazyzml 看了下 11 楼,我觉得既然是对象就不需要考虑是否是不同对象内容相同啊(除非面试官特别强调了).
    否则更极端点的,构造一个互指的对象要怎么判断呢?
    lazyzml
        18
    lazyzml  
    OP
       2018-06-01 00:11:45 +08:00
    @autoxbc 感谢。。。我才知道原来 new Set()也无法判断序列号一致。
    HuHui
        19
    HuHui  
       2018-06-01 00:13:08 +08:00 via Android
    菜鸡互啄
    rabbbit
        20
    rabbbit  
       2018-06-01 00:30:03 +08:00
    请教个问题,indexOf 的时间复杂度为什么是 O(n^2),我以为是 O(n)?
    lazyzml
        21
    lazyzml  
    OP
       2018-06-01 00:35:03 +08:00
    @rabbbit 我猜因为 indexOf 内部循环了一遍
    fulvaz
        22
    fulvaz  
       2018-06-01 00:37:29 +08:00
    @lazyzml 因为两个对象内存地址不一样的, 你又没说两个内容相同的视为同样对象.

    即使是加上了这个要求还是能搞, 缺陷是, 如果对象内有函数就不行了, 而且存在循环引用也不行

    ````
    arr.reduce((p, n) => {
    if (typeof n === 'object') {

    }

    return p.indexOf(n) === -1 ? [...p, n] : p;
    }, [])
    ````
    fulvaz
        23
    fulvaz  
       2018-06-01 00:44:44 +08:00
    手滑手滑

    ````
    arr.reduce((p, n) => {
    if (typeof n === 'object') {
    n = JSON.stringify(n);
    }
    return p.indexOf(n) === -1 ? [...p, n] : p;
    }, []).map((e) => {
    const parsed = JSON.parse(e);
    if (typeof parsed === 'object') {
    return parsed;
    } else {
    return parsed;
    }
    })
    ````

    "undefined 的情况我想到了但是我不写了, 我只是来面试的, 没心情写业务."

    不过现在复杂度是几我已经不知道了, 反正爆炸 [手动捂脸]
    fulvaz
        24
    fulvaz  
       2018-06-01 00:46:19 +08:00
    深夜无聊加点科普.

    不需要函数的简单对象, 深克隆最简单的方法是 JSON.stringify, 楼主递归估计是考虑到要递归对象对比值吧.
    lazyzml
        25
    lazyzml  
    OP
       2018-06-01 00:50:03 +08:00
    @fulvaz 是啊。。。我现在正在尝试能不能比较互相引用了的对象。
    fulvaz
        26
    fulvaz  
       2018-06-01 00:55:14 +08:00
    @rabbbit 大概是对这个对象进行先序遍历, 但是需要多一个 O(n)的数组存已经遍历过的节点, 如果某节点已经存在于数组中, 则跳过这个节点, 继续访问下一个节点

    唔, 大概每个遍历出来的结果都是唯一的吧. 然后再做比较

    不过.....我写这段代码之前应该会先去找产品聊聊人生啥的.

    或者.....自己陷入怀疑人生, TM 这是什么业务.
    fulvaz
        27
    fulvaz  
       2018-06-01 00:56:53 +08:00
    @lazyzml 你可别试了, 上次我遇到这种循环引用的时候, 我直接换了种实现方法

    解法去找司徒正美的博客.

    好是好, 但是没法适应业务, 惨
    lazyzml
        28
    lazyzml  
    OP
       2018-06-01 01:02:32 +08:00
    @fulvaz 那我不试了。。。睡了,拜拜。
    wd
        29
    wd  
       2018-06-01 08:08:06 +08:00 via iPhone
    indexOf 去重的公司就别去了…
    CasualYours
        30
    CasualYours  
       2018-06-01 08:56:18 +08:00 via Android
    对象比较通过 json 转字符串不知道可不可行
    zarte
        31
    zarte  
       2018-06-01 09:36:21 +08:00
    @wd 那用啥去重?
    msg7086
        32
    msg7086  
       2018-06-01 10:04:36 +08:00
    没记错的话正确的去重做法是利用哈希表,JS 没有哈希表就扔在 Object 上咯。
    有 Set 的话用 Set 也是可以的。
    cuzfinal
        33
    cuzfinal  
       2018-06-01 10:13:20 +08:00
    旗鼓相当的对手
    Linxing
        34
    Linxing  
       2018-06-01 10:26:15 +08:00
    难道去重不是用 SET ???
    enenaaa
        35
    enenaaa  
       2018-06-01 11:19:38 +08:00
    感觉递归和 indexOf 是差不多的消耗时间。因为内置函数的缘故,可能 indexOf 还快一点。
    doublelam
        36
    doublelam  
       2018-06-01 12:28:32 +08:00
    @CasualYours 如果有 key 值含有 undefined 或者 function 就不行
    KuroNekoFan
        37
    KuroNekoFan  
       2018-06-01 15:01:32 +08:00
    感觉首先要定义怎么算'重',当然,一般都只考虑基本类型
    njwangchuan
        38
    njwangchuan  
       2018-06-09 15:51:31 +08:00
    @lazyzml 我来帮面试官补充下他的思路:

    arr.filter((item,index) => arr.indexOf(item) == index);
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3817 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 00:15 · PVG 08:15 · LAX 16:15 · JFK 19:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.