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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐关注

› Meteor

› JSLint - a JavaScript code quality tool

› jsFiddle

› D3.js

› WebStorm

推荐书目

› JavaScript 权威指南第 5 版

› Closure: The Definitive Guide

这是一个创建于 2368 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

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

indexOf

面试

匹配

arr

38 条回复 • 2018-06-09 15:51:31 +08:00

fulvaz

2018-05-31 22:40:21 +08:00

肯定是数组去重呀, 对象就没重的啊?

lazyzml

2018-05-31 22:42:08 +08:00

@fulvaz 就是数组去重，不过数组里面可能包含对象啊。

Via8veritas

2018-05-31 22:42:33 +08:00

好像\w 数字也可以？
不过这样的公司没进去是好事吧。

uxstone

2018-05-31 22:44:38 +08:00

lodash _.uniq()

yangqi

2018-05-31 22:45:56 +08:00

\w 你说的也不对，匹配的是 word, 等同于[A-Za-z0-9_]

lazyzml

2018-05-31 22:47:17 +08:00

@yangqi 确实，我也没说对。

yangqi

2018-05-31 22:47:24 +08:00

如果是大写的\W, 那就是 not word, 就是那些符号啥的，你确定你大小写没看错？

xy90321

2018-05-31 22:47:31 +08:00

你首先得搞清楚是 \w 还是 \W 然后再讨论...

你们俩说的都不是一个东西那当然没得谈了

ryd994

2018-05-31 23:28:43 +08:00 via Android

新建一个数组然后插入前 indexof 吧
从计算复杂度上来讲和递归一样 O(n^2)
空间复杂读上来讲还不够好

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

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

递归确实难维护一点，所以文档要写清楚递归的设计，比如不变式，终止条件。而且递归一定可以用循环实现。能转成尾递归的，就可以转成很简单的循环。所以递归不推荐用。
但是要说“递归那么复杂的”，呵呵呵。

earendil1412

2018-05-31 23:34:30 +08:00 via Android

第二题的面试官答案要笑死我，空间 On 时间 On^2，能不能更牛逼一点，来个猴子去重我看不错

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

2018-05-31 23:49:44 +08:00

@fulvaz 是我没用对吗？还是没成功去重。
[截图](

)

Chingim

2018-05-31 23:52:25 +08:00 via Android

@fulvaz 楼主的意思是 indexOf 不能比较两个值相等的对象

rabbbit

2018-05-31 23:56:53 +08:00

不可以比较对象吗?

lazyzml

2018-06-01 00:04:06 +08:00

@rabbbit 你这个 a 指向同一个内存地址了。。。所以 indexOf 不会返回-1

autoxbc

2018-06-01 00:05:16 +08:00

一般去重的说法，不把序列化一致看做重复值；何况 new Set(arr) 也无法判断序列化一致，所以楼主两种方法是矛盾的

rabbbit

2018-06-01 00:09:17 +08:00

@lazyzml 看了下 11 楼,我觉得既然是对象就不需要考虑是否是不同对象内容相同啊(除非面试官特别强调了).
否则更极端点的,构造一个互指的对象要怎么判断呢?

lazyzml

2018-06-01 00:11:45 +08:00

@autoxbc 感谢。。。我才知道原来 new Set()也无法判断序列号一致。

HuHui

2018-06-01 00:13:08 +08:00 via Android

菜鸡互啄

rabbbit

2018-06-01 00:30:03 +08:00

请教个问题,indexOf 的时间复杂度为什么是 O(n^2),我以为是 O(n)?

lazyzml

2018-06-01 00:35:03 +08:00

@rabbbit 我猜因为 indexOf 内部循环了一遍

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

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

2018-06-01 00:46:19 +08:00

深夜无聊加点科普.

不需要函数的简单对象, 深克隆最简单的方法是 JSON.stringify, 楼主递归估计是考虑到要递归对象对比值吧.

lazyzml

2018-06-01 00:50:03 +08:00

@fulvaz 是啊。。。我现在正在尝试能不能比较互相引用了的对象。

fulvaz

2018-06-01 00:55:14 +08:00

@rabbbit 大概是对这个对象进行先序遍历, 但是需要多一个 O(n)的数组存已经遍历过的节点, 如果某节点已经存在于数组中, 则跳过这个节点, 继续访问下一个节点

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

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

或者.....自己陷入怀疑人生, TM 这是什么业务.

fulvaz

2018-06-01 00:56:53 +08:00

@lazyzml 你可别试了, 上次我遇到这种循环引用的时候, 我直接换了种实现方法

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

好是好, 但是没法适应业务, 惨

lazyzml

2018-06-01 01:02:32 +08:00

@fulvaz 那我不试了。。。睡了，拜拜。