数组去重

V2EX = way to explore

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

现在注册

已注册用户请登录

推荐关注

› Meteor

› JSLint - a JavaScript code quality tool

› jsFiddle

› D3.js

› WebStorm

推荐书目

› JavaScript 权威指南第 5 版

› Closure: The Definitive Guide

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

 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)😂

this

var

遍历

ype

49 条回复 • 2019-07-23 09:13:03 +08:00

zhao7399686

2019-07-18 20:23:03 +08:00

NewDraw

2019-07-18 20:27:56 +08:00 via Android

这代码是在养蛊啊！

AlloVince

2019-07-18 20:31:27 +08:00

``` js
Array.from(new Set(inputArray));
```

wenjay

2019-07-18 20:35:51 +08:00

发出去的文章不能修改的吗？

wunonglin

2019-07-18 20:37:12 +08:00

@AlloVince +1

wenjay

2019-07-18 20:37:19 +08:00

@AlloVince ES6 就是如此简单，不过面试老喜欢问这个问题，要如何回答才能显得高级呢😂

Yumwey

2019-07-18 20:48:49 +08:00

用 filter 一行就写完了

starsriver

2019-07-18 20:58:19 +08:00 via Android

es6 new 的 array 自动去重。

wenjay

2019-07-18 21:02:19 +08:00

https://www.v2ex.com/faq

lihongjie0209

2019-07-18 21:09:12 +08:00

数据结构没学好?

xingyue

2019-07-18 21:31:29 +08:00

我这是要完犊子了吗，看了半天没觉得有什么问题.....除了代码啰嗦了点。再看看 #1 #2 #10，现在内心慌的一.....

taogen

2019-07-18 21:41:33 +08:00 via Android

就说算法的时间复杂度为 O(n^2)，空间复杂度为 O(n)。高级否？

taogen

2019-07-18 21:49:44 +08:00 via Android

另外，用 hash table 作为中间容器，时间复杂度可以为 O(n)

oIMOo

2019-07-18 22:55:24 +08:00

转成 set 再转回 list 怎么样？

lynnic

2019-07-18 23:01:30 +08:00 via Android

时间复杂度为啥是 n 方？

necomancer

2019-07-18 23:07:05 +08:00

@lynnic indexof 是 o(n) 的吧

kyuuseiryuu

2019-07-18 23:54:09 +08:00 via iPhone

@necomancer 外面还有一层 n🤣

serenader

2019-07-19 00:04:42 +08:00

LZ 的这个方法有个 bug，无法去重 NaN 以及 {} 。

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

不过刚刚看了一下，我文章里面最后给出的方案也有 bug。。纯粹当抛砖引玉了，看看大家能找到几个 bug 🤣🤣

indomi

2019-07-19 00:26:16 +08:00

[...new Set(arr)]

bumz

2019-07-19 09:15:41 +08:00 via iPhone

ES6 之前就手写一哈希表，高级吗，手动狗头

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

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

2019-07-19 10:13:57 +08:00

后排吃瓜

karllynn

2019-07-19 10:48:11 +08:00

用 hash 的话，数组的顺序会变的…楼主这个时间复杂度太高了

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

2019-07-19 11:18:45 +08:00

@QiaTia 多打了一个点 if (n[this[i]] !== 'a')

dartabe

2019-07-19 11:45:12 +08:00

之前在写 leetcode 的时候用的 set 做的中间容器. 时间复杂度 O(n)

后来发现 set 自动就可以去重了

dartabe

2019-07-19 12:07:08 +08:00

不过 javascript 对象直接就是哈希表了？用 set 的话我只是懒得存 1/0 或者 true /false

求大佬看我理解对不对

weixiangzhe

2019-07-19 12:16:26 +08:00 via iPhone

这种东西直接看 lodash 源码最靠谱了

reus

2019-07-19 12:21:23 +08:00

把 indexOf 改成对 Set 的操作，用 Set 辅助去重
如果没有 Set，那就自己实现一个

CodingNaux

2019-07-19 12:22:40 +08:00 via iPhone

unique （ collection，func)

RoshanWu

2019-07-19 12:24:32 +08:00

https://gist.github.com/9099d784a0727aae1228142f340b6475#file-unique-js

RoshanWu

2019-07-19 12:25:29 +08:00

https://gist.github.com/roshanca/9099d784a0727aae1228142f340b6475

wozhizui

2019-07-19 12:27:56 +08:00

@oIMOo 俺也一样

Arizas

2019-07-19 12:34:18 +08:00

uniqueResult = [...new Set(arr)]

Aoerz

2019-07-19 13:32:55 +08:00 via Android

首先排序，然后遍历，时间复杂度 O(n)，空间复杂度 O(1)

Snail233

2019-07-19 13:39:56 +08:00

es6 不是有 set 么、

lihongjie0209

2019-07-19 13:44:05 +08:00

@Aoerz
排序的 nlogn 的时间复杂度不算了?

Fairy1128

2019-07-19 14:56:46 +08:00

难道不是先问数组的 item 是普通类型还是引用类型吗

Laumm

2019-07-19 16:04:13 +08:00

@Aoerz 既然都需要排序了，时间复杂度就应该大于 O(n)

Laumm

2019-07-19 16:04:39 +08:00

感觉最简单就是放 Set 里了

arnoldxiao

2019-07-19 16:14:21 +08:00

用 Set 含一下再放回去

fengdechoulian

2019-07-19 16:22:34 +08:00

@arnoldxiao 仰望高端玩家

doing1

2019-07-19 16:45:37 +08:00

我服了

Aoerz

2019-07-19 17:00:07 +08:00 via Android

@Laumm 是的，把排序这茬给忘了

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

2019-07-19 18:30:20 +08:00 via iPhone

不能先排序吧，数组里可能有数字可能有字符串或者其它任何东西

YouMoeYi

2019-07-19 18:50:31 +08:00

为啥不用 Set
function arr_dr (arr){
let st = new Set(arr);
return [...st];
}

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 }