首先第一个问题是\w 匹配什么,我说的匹配小写 a-z,然后他说不对,是匹配空格,tab 符那些。
然后第二个问题是 js 如何数组去重
我回答第一个方法是 new Set(arr)去重,第二个方法是通过递归然后比较。我主要考虑到了对象。 面试官大意是何必用递归那么复杂的,直接再建一个数组,然后 indexOf 判断。我当时想,哎,没想到用 indexOf 判断,现在想来,indexOf 并不能比较对象,面试官说错了。
1
fulvaz 2018-05-31 22:40:21 +08:00
肯定是数组去重呀, 对象就没重的啊?
|
3
Via8veritas 2018-05-31 22:42:33 +08:00
好像\w 数字也可以?
不过这样的公司没进去是好事吧。 |
4
uxstone 2018-05-31 22:44:38 +08:00
lodash _.uniq()
|
5
yangqi 2018-05-31 22:45:56 +08:00
\w 你说的也不对,匹配的是 word, 等同于[A-Za-z0-9_]
|
7
yangqi 2018-05-31 22:47:24 +08:00
如果是大写的\W, 那就是 not word, 就是那些符号啥的,你确定你大小写没看错?
|
8
xy90321 2018-05-31 22:47:31 +08:00
你首先得搞清楚是 \w 还是 \W 然后再讨论...
你们俩说的都不是一个东西那当然没得谈了 |
9
ryd994 2018-05-31 23:28:43 +08:00 via Android
新建一个数组然后插入前 indexof 吧
从计算复杂度上来讲和递归一样 O(n^2) 空间复杂读上来讲还不够好 好的办法: 两个指针,一个指向读的位置,一个指向写的位置 写之前扫描 [0,写],有重复就 pass O(1)空间 计算复杂度最低应该就是 Set O(nlogn) 递归确实难维护一点,所以文档要写清楚递归的设计,比如不变式,终止条件。而且递归一定可以用循环实现。能转成尾递归的,就可以转成很简单的循环。所以递归不推荐用。 但是要说“递归那么复杂的”,呵呵呵。 |
10
earendil1412 2018-05-31 23:34:30 +08:00 via Android
第二题的面试官答案要笑死我,空间 On 时间 On^2,能不能更牛逼一点,来个猴子去重我看不错
|
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 的复杂度是啥?) |
14
rabbbit 2018-05-31 23:56:53 +08:00
|
16
autoxbc 2018-06-01 00:05:16 +08:00
一般去重的说法,不把序列化一致看做重复值;何况 new Set(arr) 也无法判断序列化一致,所以楼主两种方法是矛盾的
|
17
rabbbit 2018-06-01 00:09:17 +08:00
|
19
HuHui 2018-06-01 00:13:08 +08:00 via Android
菜鸡互啄
|
20
rabbbit 2018-06-01 00:30:03 +08:00
请教个问题,indexOf 的时间复杂度为什么是 O(n^2),我以为是 O(n)?
|
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; }, []) ```` |
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 的情况我想到了但是我不写了, 我只是来面试的, 没心情写业务." 不过现在复杂度是几我已经不知道了, 反正爆炸 [手动捂脸] |
24
fulvaz 2018-06-01 00:46:19 +08:00
深夜无聊加点科普.
不需要函数的简单对象, 深克隆最简单的方法是 JSON.stringify, 楼主递归估计是考虑到要递归对象对比值吧. |
26
fulvaz 2018-06-01 00:55:14 +08:00
@rabbbit 大概是对这个对象进行先序遍历, 但是需要多一个 O(n)的数组存已经遍历过的节点, 如果某节点已经存在于数组中, 则跳过这个节点, 继续访问下一个节点
唔, 大概每个遍历出来的结果都是唯一的吧. 然后再做比较 不过.....我写这段代码之前应该会先去找产品聊聊人生啥的. 或者.....自己陷入怀疑人生, TM 这是什么业务. |
27
fulvaz 2018-06-01 00:56:53 +08:00
|
29
wd 2018-06-01 08:08:06 +08:00 via iPhone
indexOf 去重的公司就别去了…
|
30
CasualYours 2018-06-01 08:56:18 +08:00 via Android
对象比较通过 json 转字符串不知道可不可行
|
32
msg7086 2018-06-01 10:04:36 +08:00
没记错的话正确的去重做法是利用哈希表,JS 没有哈希表就扔在 Object 上咯。
有 Set 的话用 Set 也是可以的。 |
33
cuzfinal 2018-06-01 10:13:20 +08:00
旗鼓相当的对手
|
34
Linxing 2018-06-01 10:26:15 +08:00
难道去重不是用 SET ???
|
35
enenaaa 2018-06-01 11:19:38 +08:00
感觉递归和 indexOf 是差不多的消耗时间。因为内置函数的缘故,可能 indexOf 还快一点。
|
36
doublelam 2018-06-01 12:28:32 +08:00
@CasualYours 如果有 key 值含有 undefined 或者 function 就不行
|
37
KuroNekoFan 2018-06-01 15:01:32 +08:00
感觉首先要定义怎么算'重',当然,一般都只考虑基本类型
|
38
njwangchuan 2018-06-09 15:51:31 +08:00
|