鸦杀's Blog

一道面试题——数组去重且不保留重复元素

2018-08-20

今天遇到的面试题,数组中都元素一旦重复,就全部删除,只保留未重复的元素,与常规去重还是有一丢丢不同的。应用场景嘛,比如说刷单去重复手机号??(不管了,也可能是面试官看到我欣喜的表情灵机一动~~)

面试官现场问的,当时想的方案就是多次循环啦,第一次生成对象,标记次数。第二次循环对象生成数组。但也知道这种方案其实是不太适合的,毕竟数值生成的key会变成字符串,对象生成的key会变成[object Object],至于数组就更不可控了。

方案一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function filterRepeat(arr) {
var obj = {}
var result = []
for(var i = 0; i<arr.length; i++) {
var v = arr[i]
if (!obj[v]) {
obj[v] = 1
} else {
obj[v]++
}
}
for(var k in obj) {
if (obj.hasOwnProperty(k)) {
if(obj[k] === 1) {
result.push(k)
}
}
}
return result
}
// 结果不可预测
filterRepeat(['a', 'b', 'c', 'b', 'd', 'b','d'])
// ["a", "c"]
filterRepeat(['a', 'b', 'c', 'b', 'd', 'b','d', {a: 1},{b:1},['a'],['b']])
// ["c"]

回家想了想,其实有更好的方案,做标记还是用set、map比较靠谱,也没必要使用二重循环~
思路就是先按顺序从数组删除一个元素,查找该元素在数组中的下标,如果找得到,添加到set中,并删除该下标元素。如果找不到且不在set中,说明是唯一的,添加到结果数组中,最后返回结果数组

方案二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var myArr = ['a', 'b', 'c', 'b', 'd', 'b','d']
function filterRepeat2(arr) {
arr = [...arr]
var result = []
var set = new Set()
while(arr.length) {
var temp = arr.shift()
var index = arr.indexOf(temp)
if ( index!== -1) {
arr.splice(index, 1)
set.add(temp)
} else {
if (!set.has(temp)) {
result.push(temp)
}
}
}
return result
}
filterRepeat2(myArr)
// ['a', 'c']

方案三:利用set先获取不重复的数组,遍历不重复数组,判断其中哪些元素是在原数组中多次出现的。如果找到,从不重复数组中删除。优点是代码量比方案二少一点,思路上我觉得差不多,反正都用了set和数组的splice、indexOf方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var myArray = ['a', 'b', 'c', 'b', 'd', 'b','d']
function filterRepeat3(arr) {
arr = [...arr]
var norepeat = [...new Set(arr)]
for(var i = norepeat.length - 1; i>0;i--) {
var v = norepeat[i]
arr.splice(arr.indexOf(v), 1)
if (arr.indexOf(v)!== -1) {
norepeat.splice(i, 1)
}
}
return norepeat
}
filterRepeat3(myArray)
// ['a', 'c']

进一步的改进,其实方案2、3还是有问题的,比如数组中含有NaN的时候。

1
2
filterRepeat2([NaN, NaN])
// [NaN, NaN]

解决方案是把indexOf方法改成findIndex结合Object.is啦~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var myArray = ['a', 'b', 'c', 'b', 'd', 'b','d',NaN, NaN]

function filterRepeat3(arr) {
arr = [...arr]
var norepeat = [...new Set(arr)]
for(var i = norepeat.length - 1; i>0;i--) {
var v = norepeat[i]
arr.splice(arr.findIndex(it => Object.is(v, it)), 1)
if (arr.findIndex(it => Object.is(v, it))!== -1) {
norepeat.splice(i, 1)
}
}
return norepeat
}
filterRepeat3(myArray)
// ["a", "c"]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function filterRepeat2(arr) {
arr = [...arr]
var result = []
var set = new Set()
while(arr.length) {
var temp = arr.shift()
var index = arr.findIndex(it => Object.is(temp, it))
if ( index!== -1) {
arr.splice(index, 1)
set.add(temp)
} else {
if (!set.has(temp)) {
result.push(temp)
}
}
}
return result
}
filterRepeat2(['a', 'b', 'c', 'b', 'd', 'b','d',NaN, NaN])
// ['a', 'c']

等等,这样就完美了么?
我想到了+0,和 -0,毕竟它在set中是被认为相等的,在Object.is和全等比较的结果也不同。

看下面这段输出

1
2
3
4
5
6
7
8
Object.is(0, -0)
// false
Object.is(0, +0)
// true
0 === +0
// true
0 === -0
// true

我对改进过的方案二和方案三,调用一个包含+0和 -0的数组,结果会是什么呢?

1
2
3
4
5
6
// 方案二
filterRepeat2(['a', 'b', 'c', 'b', 'd', 'b','d',NaN, NaN, +0, -0])
// (4) ["a", "c", 0, -0]
// 方案三
filterRepeat3(['a', 'b', 'c', 'b', 'd', 'b','d',NaN, NaN, +0, -0])
// (3) ["a", "c", 0]

现在你应该有了答案。方案二其实是优于方案三的。。。

扫描二维码,分享此文章