{{ message }}

# JavaScript专题之数组去重 #27

Open
opened this issue Jun 21, 2017 · 89 comments
Open

# JavaScript专题之数组去重#27

opened this issue Jun 21, 2017 · 89 comments
Labels

## 双层循环

```var array = [1, 1, '1', '1'];

function unique(array) {
// res用来存储结果
var res = [];
for (var i = 0, arrayLen = array.length; i < arrayLen; i++) {
for (var j = 0, resLen = res.length; j < resLen; j++ ) {
if (array[i] === res[j]) {
break;
}
}
// 如果array[i]是唯一的，那么执行完循环，j等于resLen
if (j === resLen) {
res.push(array[i])
}
}
return res;
}

console.log(unique(array)); // [1, "1"]```

## indexOf

```var array = [1, 1, '1'];

function unique(array) {
var res = [];
for (var i = 0, len = array.length; i < len; i++) {
var current = array[i];
if (res.indexOf(current) === -1) {
res.push(current)
}
}
return res;
}

console.log(unique(array));```

## 排序后去重

```var array = [1, 1, '1'];

function unique(array) {
var res = [];
var sortedArray = array.concat().sort();
var seen;
for (var i = 0, len = sortedArray.length; i < len; i++) {
// 如果是第一个元素或者相邻的元素不相同
if (!i || seen !== sortedArray[i]) {
res.push(sortedArray[i])
}
seen = sortedArray[i];
}
return res;
}

console.log(unique(array));```

## unique API

```var array1 = [1, 2, '1', 2, 1];
var array2 = [1, 1, '1', 2, 2];

// 第一版
function unique(array, isSorted) {
var res = [];
var seen = [];

for (var i = 0, len = array.length; i < len; i++) {
var value = array[i];
if (isSorted) {
if (!i || seen !== value) {
res.push(value)
}
seen = value;
}
else if (res.indexOf(value) === -1) {
res.push(value);
}
}
return res;
}

console.log(unique(array1)); // [1, 2, "1"]
console.log(unique(array2, true)); // [1, "1", 2]```

## 优化

```var array3 = [1, 1, 'a', 'A', 2, 2];

// 第二版
// iteratee 英文释义：迭代 重复
function unique(array, isSorted, iteratee) {
var res = [];
var seen = [];

for (var i = 0, len = array.length; i < len; i++) {
var value = array[i];
var computed = iteratee ? iteratee(value, i, array) : value;
if (isSorted) {
if (!i || seen !== computed) {
res.push(value)
}
seen = computed;
}
else if (iteratee) {
if (seen.indexOf(computed) === -1) {
seen.push(computed);
res.push(value);
}
}
else if (res.indexOf(value) === -1) {
res.push(value);
}
}
return res;
}

console.log(unique(array3, false, function(item){
return typeof item == 'string' ? item.toLowerCase() : item
})); // [1, "a", 2]```

array：表示要去重的数组，必填

isSorted：表示函数传入的数组是否已排过序，如果为 true，将会采用更快的方法进行去重

iteratee：传入一个函数，可以对每个元素进行重新的计算，然后根据处理的结果进行去重

## filter

ES5 提供了 filter 方法，我们可以用来简化外层循环：

```var array = [1, 2, 1, 1, '1'];

function unique(array) {
var res = array.filter(function(item, index, array){
return array.indexOf(item) === index;
})
return res;
}

console.log(unique(array));```

```var array = [1, 2, 1, 1, '1'];

function unique(array) {
return array.concat().sort().filter(function(item, index, array){
return !index || item !== array[index - 1]
})
}

console.log(unique(array));```

## Object 键值对

```var array = [1, 2, 1, 1, '1'];

function unique(array) {
var obj = {};
return array.filter(function(item, index, array){
return obj.hasOwnProperty(item) ? false : (obj[item] = true)
})
}

console.log(unique(array)); // [1, 2]```

```var array = [1, 2, 1, 1, '1'];

function unique(array) {
var obj = {};
return array.filter(function(item, index, array){
return obj.hasOwnProperty(typeof item + item) ? false : (obj[typeof item + item] = true)
})
}

console.log(unique(array)); // [1, 2, "1"]```

```var array = [{value: 1}, {value: 1}, {value: 2}];

function unique(array) {
var obj = {};
return array.filter(function(item, index, array){
console.log(typeof item + JSON.stringify(item))
return obj.hasOwnProperty(typeof item + JSON.stringify(item)) ? false : (obj[typeof item + JSON.stringify(item)] = true)
})
}

console.log(unique(array)); // [{value: 1}, {value: 2}]```

## ES6

```var array = [1, 2, 1, 1, '1'];

function unique(array) {
return Array.from(new Set(array));
}

console.log(unique(array)); // [1, 2, "1"]```

```function unique(array) {
return [...new Set(array)];
}```

`var unique = (a) => [...new Set(a)]`

```function unique (arr) {
const seen = new Map()
return arr.filter((a) => !seen.has(a) && seen.set(a, 1))
}```

## 特殊类型比较

```var str1 = '1';
var str2 = new String('1');

console.log(str1 == str2); // true
console.log(str1 === str2); // false

console.log(null == null); // true
console.log(null === null); // true

console.log(undefined == undefined); // true
console.log(undefined === undefined); // true

console.log(NaN == NaN); // false
console.log(NaN === NaN); // false

console.log(/a/ == /a/); // false
console.log(/a/ === /a/); // false

console.log({} == {}); // false
console.log({} === {}); // false```

`var array = [1, 1, '1', '1', null, null, undefined, undefined, new String('1'), new String('1'), /a/, /a/, NaN, NaN];`

for循环 [1, "1", null, undefined, String, String, /a/, /a/, NaN, NaN] 对象和 NaN 不去重
indexOf [1, "1", null, undefined, String, String, /a/, /a/, NaN, NaN] 对象和 NaN 不去重
sort [/a/, /a/, "1", 1, String, 1, String, NaN, NaN, null, undefined] 对象和 NaN 不去重 数字 1 也不去重
filter + indexOf [1, "1", null, undefined, String, String, /a/, /a/] 对象不去重 NaN 会被忽略掉
filter + sort [/a/, /a/, "1", 1, String, 1, String, NaN, NaN, null, undefined] 对象和 NaN 不去重 数字 1 不去重

Set [1, "1", null, undefined, String, String, /a/, /a/, NaN] 对象不去重 NaN 去重

```// demo1
var arr = [1, 2, NaN];
arr.indexOf(NaN); // -1```

indexOf 底层还是使用 === 进行判断，因为 NaN === NaN的结果为 false，所以使用 indexOf 查找不到 NaN 元素

```// demo2
function unique(array) {
return Array.from(new Set(array));
}
console.log(unique([NaN, NaN])) // [NaN]```

Set 认为尽管 NaN === NaN 为 false，但是这两个元素是重复的。

## 专题系列

JavaScript专题系列目录地址：https://github.com/mqyqingfeng/Blog

JavaScript专题系列预计写二十篇左右，主要研究日常开发中一些功能点的实现，比如防抖、节流、去重、类型判断、拷贝、最值、扁平、柯里、递归、乱序、排序等，特点是研(chao)究(xi) underscore 和 jQuery 的实现方式。

We are unable to convert the task to an issue at this time. Please try again.

 赞

### zeroone001 commented Jun 29, 2017

 有个小问题，关于排序后去重的下面的代码，`var sortedArray = array.concat().sort();` 这个concat()在这里的意义是什么？不是很理解～

### jochenshi commented Jun 29, 2017

 @zeroone001 你对数组进行了 array.concat()操作之后，相当于复制出来一份原有的数组，且对复制出来的新数组的操作不会影响到原有数组，但是上面的这个去重的方法是有问题的，对有些数组就无法排序

### jochenshi commented Jun 29, 2017

 建议文章中对于用到sort来进行排序的地方都看一下，这些地方的排序的方法是有错误的

### mqyqingfeng commented Jun 29, 2017

 @jochenshi 感谢回答哈，全文只有 sort 排序那里使用了排序，sort 排序的结果并不总是正确的，从文章最后的特殊类型排序结果表中，也可以看出，我应该专门注明这个问题的。sort 之所以会出错，还是因为 sort 的原理所致，我会在这个系列的大约第 19 篇中讲讲 V8 的排序源码。之所以写排序去重，是为了引出 underscore 的 unique API，在这个 API 中，如果是处理已排序好的数组，就可以传 true，使用更快的去重方法，而数组是怎么排序的，underscore 并不提供，为了演示排序去重的原理，我才简便的使用了 sort 方法，对数组进行了排序，因为使用了 sort，当涉及到特殊类型时，会出现问题，只能说明使用的场景其实是有限的，也不能说就是错误的，当然真到项目开发中，还是要用类似 underscore、lodash 提供的功能。最后感谢指出哈~ o(￣▽￣)ｄ

### YeaseonZhang commented Jul 13, 2017

 第二版是不是逻辑不太清晰，应该修改为 ``````var array3 = [1, 1, 'a', 'A', 2, 2]; // 第二版 // iteratee 英文释义：迭代 重复 function unique(array, isSorted, iteratee) { var res = []; var seen = []; for (var i = 0, len = array.length; i < len; i++) { var value = array[i]; var computed = iteratee ? iteratee(value, i, array) : value; if (isSorted) { if (!i || seen !== computed ) { res.push(computed ) } seen = computed ; } else if (res.indexOf(computed ) === -1) { res.push(computed ); } } return res; } console.log(unique(array3, false, function(item){ return typeof item == 'string' ? item.toLowerCase() : item })); // [1, "a", 2] `````` 如果指出有错误，还请见谅。

### mqyqingfeng commented Jul 13, 2017

 @YeaseonZhang 两个函数实现的效果不一样哈~ 举个例子： ```var array = [{value: 1}, {value: 2}, {value: 1}]; console.log(unique(array, false, function(item){ return item.value }));``` 如果使用文章中的方法，结果会是 [{value: 1}, {value: 2}] 如果使用你的方法，结果会是 [1, 2] 区别在于使用迭代函数处理后的元素，去重后，是返回以前的元素还是计算后的元素。 无所谓对错，看你想设计成什么样子。

### YeaseonZhang commented Jul 13, 2017

 @mqyqingfeng 谢谢回复，确实像你给出的那个例子一样。

### FrontToEnd commented Jul 13, 2017

 请教大神一个问题，为什么正则/a/相等和全等都是false呢

### mqyqingfeng commented Jul 13, 2017

 @FrontToEnd 因为在 JavaScript 中，正则表达式也是对象。

### FrontToEnd commented Jul 13, 2017

 @mqyqingfeng 谢谢提醒，差点忘了。😯
mentioned this issue Aug 9, 2017

### suihaohao commented Aug 22, 2017

 多维数组如何去重呢？

### mqyqingfeng commented Aug 22, 2017

 @suihaohao 也可以先扁平再去重，关于扁平化： JavaScript专题之数组扁平化

### suihaohao commented Aug 22, 2017

 扁平之后再去重那就不是多维数组了吧，但是我想要的是去重之后仍然是多维数组呢？

### mqyqingfeng commented Aug 24, 2017 • edited

 @suihaohao 如果是这样的话，遍历的时候判断元素是否是数组，然后递归使用 unique 函数，类似于这样： ``` var array = [1, 2, 1, [1, 1, 2], [3, 3, 4]]; function unique(array) { var res = []; for (var i = 0, len = array.length; i < len; i++) { var current = array[i]; if (Array.isArray(array[i])) { res.push(unique(array[i])) } else if (res.indexOf(current) === -1) { res.push(current) } } return res; } console.log(unique(array)); // [1, 2, [1, 2], [3, 4]]```

### suihaohao commented Aug 24, 2017

 @mqyqingfeng 但是如果是 var array = [1, 2, 1, [1, 1, 2], [3, 3, 4],[1, 1, 2]]这样的数组，我想要的结果是 res= [1, 2, [1, 2], [3, 4]];这个方法就不行了；

### mqyqingfeng commented Aug 24, 2017

 @suihaohao 其实你想要的并不是多维数组的去重，而是对象的去重，这需要再利用一个判断两个对象是否相等的函数，JavaScript专题之如何判断两个对象相等

### mqyqingfeng commented Aug 24, 2017

 @suihaohao 如果是要这个结果的话，你可以先利用键值对去重的方法处理成 [1, 2, [1,1, 2], [3, 3, 4]]，再利用刚才的多维数组去重的方法，处理成 [1, 2, [1, 2], [3, 4]]

### suihaohao commented Aug 24, 2017

 @mqyqingfeng 灰常感谢！！！

### suihaohao commented Aug 24, 2017

 @mqyqingfeng 大神辛苦了

### huangmxsysu commented Sep 4, 2017

 Object键值对方法中的键应改成typeof item + JSON.stringify(item) 不然的话{}，跟{name:'mosen'}会当成一样的因为如果是typeof item + item的话键都是object[object Object]

### mqyqingfeng commented Sep 5, 2017

 @huangmxsysu 感谢指出，确实有这个问题~

### lowerfish commented Sep 12, 2017

 最后一版感觉有点问题 ``````function unique(array, isSorted, iteratee) { var res = []; var seen = []; for (var i = 0, len = array.length; i < len; i++) { var value = array[i]; var computed = iteratee ? iteratee(value, i, array) : value; if (isSorted) { if (!i || seen !== computed) { res.push(value) } seen = computed; } else if (iteratee) { if (seen.indexOf(computed) === -1) { seen.push(computed); res.push(value); } } else if (res.indexOf(value) === -1) { res.push(value); } } return res; } `````` 修改前 ``````var arr = ['A','a',1].sort(); unique(arr,true,function(item){ return typeof item == 'string' ? item.toLowerCase() : item }); // [ 1, 'A', 'a' ] `````` 如果不做修改的话，一个排序过的数组，传不传入 iteratee 方法，对运行结果没啥影响啊。

### mqyqingfeng commented Sep 12, 2017

 @yepbug，我试了一下，结果是 [1, "A"]，没有问题哈，unique 函数会返回一个新的数组，你是不是打印了 arr 数组？

### lowerfish commented Sep 12, 2017

 @mqyqingfeng 没有···· 你运行的是不是修改过的代码哈······ 这是文章中最后一版的代码： ``````function unique(array, isSorted, iteratee) { var res = []; var seen = []; for (var i = 0, len = array.length; i < len; i++) { var value = array[i]; var computed = iteratee ? iteratee(value, i, array) : value; // 我觉得这里有点问题 // 如果不做修改的话，一个排序过的数组，传不传入 iteratee 方法，对运行结果没啥影响啊。 if (isSorted) { if (!i || seen !== value) { res.push(value) } seen = value; } else if (iteratee) { if (seen.indexOf(computed) === -1) { seen.push(computed); res.push(value); } } else if (res.indexOf(value) === -1) { res.push(value); } } return res; } `````` 如果按照上面的代码，来处理一个简单排序过的数组的时候，会有点小问题： ``````var arr = ['A','a',1].sort();//按数字字母排序 => [1, "A", "a"] console.log(unique(arr,true,function(item){ return typeof item == 'string' ? item.toLowerCase() : item })); // 运行结果 [1, "A", "a"] ``````

### mqyqingfeng commented Sep 13, 2017 • edited

 @yepbug 哈哈~ 确实是我运行错了~ 非常感谢指出~

### ke1vinn commented May 14, 2019

 用JSON.stringify区分Object绝对是错误的，同一个对象写法里，字面量属性顺序不同JSON.stringify的结果也不同，你还要考虑对象里还有对象的情况，判断对象属性值相等本身就没这么简单
mentioned this issue May 29, 2019

### WiensHy commented Jul 15, 2019

 优化小节中，`unqique` 的拼写错了
mentioned this issue Jul 29, 2019

### Dongd0825 commented Aug 3, 2019

 function unique(array, isSorted, iteratee) { var res = []; var seen = []; ``````for (var i = 0, len = array.length; i < len; i++) { var value = array[i]; var computed = iteratee ? iteratee(value, i, array) : value; if (isSorted) { if (!i || seen !== computed) { res.push(value) } seen = computed; } else { if (seen.indexOf(computed) === -1) { seen.push(computed); res.push(value); } } } return res; `````` } @YeaseonZhang 两个函数实现的效果不一样哈~ 举个例子： ```var array = [{value: 1}, {value: 2}, {value: 1}]; console.log(unique(array, false, function(item){ return item.value }));``` 如果使用文章中的方法，结果会是 [{value: 1}, {value: 2}] 如果使用你的方法，结果会是 [1, 2] 区别在于使用迭代函数处理后的元素，去重后，是返回以前的元素还是计算后的元素。 无所谓对错，看你想设计成什么样子。 是不是可以改成这种 function unique(array, isSorted, iteratee) { var res = []; var seen = []; ``````for (var i = 0, len = array.length; i < len; i++) { var value = array[i]; var computed = iteratee ? iteratee(value, i, array) : value; if (isSorted) { if (!i || seen !== computed) { res.push(value) } seen = computed; } else { if (seen.indexOf(computed) === -1) { seen.push(computed); res.push(value); } } } return res; `````` }

### DaiZhaoedu commented Aug 21, 2019

 copy过去使用为什么出错呢?js小学生求指教

### Tutao1995 commented Aug 22, 2019

 因该是Array.filter 吧 … ------------------ 原始邮件 ------------------ 发件人: "Fedor Dai"; 发送时间: 2019年8月21日(星期三) 下午2:36 收件人: "mqyqingfeng/Blog"; 抄送: "涂滔"<851542486@qq.com>; "Comment"; 主题: Re: [mqyqingfeng/Blog] JavaScript专题之数组去重 (#27) copy过去使用为什么出错呢?js小学生求指教 — You are receiving this because you commented. Reply to this email directly, view it on GitHub, or mute the thread.
mentioned this issue Aug 23, 2019

 学习了学习了

### yinzuowen commented Sep 17, 2019

 有个小问题，关于排序后去重的下面的代码，`var sortedArray = array.concat().sort();` 这个concat()在这里的意义是什么？不是很理解～ 为了不影响原数组

### bitSeaChen commented Sep 18, 2019

 博主您好，sort 是可以过滤数字 1 的，不知道你为什么会说不能过滤了？

### ErazerControl commented Oct 10, 2019

 博主您好，sort 是可以过滤数字 1 的，不知道你为什么会说不能过滤了？ 我本来是在控制台运行的，跟你有一样的问题，后来我发现在node环境下1就没有去重，比较后发现是sort()排序出现的问题，我猜测正如前几个问题的评论一样，sort 排序的结果并不总是正确的，在node排序的结果是， `[ /a/, /a/, '1', '1', 1, [String: '1'], 1, [String: '1'], NaN, NaN, null, null, undefined, undefined ]` 两个数字1并不相邻导致1没有去重。

### thinkerHope commented Nov 2, 2019

 const uniqueWithSet = (arr) => Array.from(new Set(arr.map(item => JSON.stringify(item))), item => JSON.parse(item))这样写会不会更好呢。
mentioned this issue Mar 27, 2020
mentioned this issue Apr 2, 2020

### MoJiaBings commented Apr 7, 2020

 第三个排序去重 !i 那个判断应该是多余的吧
mentioned this issue Apr 26, 2020

### KeithChou commented Jun 10, 2020

 楼主在优化大小写版本的时候，是这样写的 新需求：字母的大小写视为一致，比如'a'和'A'，保留一个就可以了！ 这里是只保留大写或者小写中的一个就好了。所以针对`var arr = ["A", "B", "a", "b"]` 返回 `["A", "B"]` 没有毛病呀

### Dengyy commented Jul 11, 2020 • edited

sort [/a/, /a/, "1", 1, String, 1, String, NaN, NaN, null, undefined] 对象和 NaN 不去重 数字 1 也不去重
filter + sort [/a/, /a/, "1", 1, String, 1, String, NaN, NaN, null, undefined] 对象和 NaN 不去重 数字 1 也不去重

### Lxdll commented Aug 23, 2020

 楼主，第二个indexOf方法可以换成ES6的includes方法，这样就可以去掉重复的NaN，就是带来了兼容性问题。 `function unique(array){ var res = []; for(var i = 0, len = array.length; i < len; i++){ var current = array[i]; if(!res.includes(current)){ res.push(current); } } return res; }`

### Lxdll commented Aug 23, 2020

 ``````function unique(array){ var res = []; for(var i = 0, len = array.length; i < len; i++){ var current = array[i]; if(!res.includes(current)){ res.push(current); } } return res; } ``````

### vnues commented Sep 9, 2020 • edited

 ```/** * map加for循环 O(n) */ const map = {} let array = [] for (let i = 0; i < arr.length; i++) { if (map[arr[i]]) { return } array.push(arr[i]) map[arr[i]] = true }```

### zenblo commented Oct 13, 2020

 图片
mentioned this issue Oct 22, 2020

### Little-Prince-Teng commented Dec 23, 2020

 各位大佬，帮忙解释下这步

### banli17 commented Apr 3, 2021 • edited

 @Little-Prince-Teng 发现后面有重复的，就不管前面的这个了，继续往后走，只插入最右边的

### yinju123 commented May 4, 2021

 isSortd其作用是在没有iteratee的情况先把，iteratee返回的值，不一定认识排序好的 ``````function unique(arr, isSortd, iteratee) { var res = [] var seen = [] for (var i = 0, l = arr.length; i < l; i++) { var value = arr[i] // 通过iteratee计算得到的值，不一定任然是排序好的 if (isSortd && !iteratee) { if (value !== seen) { res.push(value) seen = value } } else { var computed = iteratee ? iteratee(value, i, arr) : value if (seen.indexOf(value) === -1) { res.push(value) seen.push(computed) } } } } ``````
mentioned this issue May 22, 2021

### Luoyuda commented Jun 1, 2021

 ```var array = [/a/, /a/, /b/, "1", 1, String, 1, String, NaN, NaN, null, undefined]; function unique(array) { var obj = {}; return array.filter(function(item, index, array){ console.log(typeof item + JSON.stringify(item)) return obj.hasOwnProperty(typeof item + JSON.stringify(item)) ? false : (obj[typeof item + JSON.stringify(item)] = true) }) } console.log(unique(array)) // [/a/, "1", 1, ƒ, NaN, null, undefined]``` `/b/` 会被过滤掉 按照这个方法键值是重复的 `/a/ => object{} /b/ => object{}` 这里是不是需要特判一下正则的情况 `item = item instanceof RegExp ? item.toString() : item`
mentioned this issue Jul 30, 2021