数组去重 unique
手写数组去重方法(前端应用场景中一般不会遇到数组去重,都是使用后端去重后的数据,去重仅作为考察基础知识掌握能力)
Set
实现(推荐)- [
for
,for...of
,forEach
,filter
] + [indexOf
,includes
,for
] 组合实现 - [
reduce
] + [indexOf
,includes
] 实现 sort
+for
实现(利用底层 sort)- 遍历 +
hasOwnProperty
结合缓存实现(有限制) - 遍历 +
Map
缓存实现(推荐) - 扩展: 对象数组去重
- 基于某个对象属性去重
- 简单对象数组去重(对象为 json 数据)
- 基于宽松相等(内容完全相等)去重
- 主要考虑实现 looseEqual
1. Set
实现
Set
对象 Set
确保值列表的唯一性,无论是原始值或者是对象引用。
- 值的相等(
Set
使用SameValueZero
比较算法来区分不同的值。不是基于===
也不是Object.is
)- 对于
Set
,+0
严格相等于-0
- 对于
===
, ES2015 规范中更改为+0 严格相等于-0
Object.is(+0, -0)
输出false
- 对于
Set
中,NaN
被认为是相同的, 不同于===
- 对于
SameValueZero
零值相等算法,同同值相等 Object.is()
方法类似,不过会认为 +0
与 -0
相等。
更多参看
- MDN Set
- MDN 相等性判断
- ECMA-262 SameValueZero
- ECMA-262 Set Objects
2. for
+ indexOf
实现
通过 for
实现双层循环遍历比对,foreach
, filter
类似
indexOf()
使用严格相等 ===
与 Array 的元素进行比较。这个不同于 SameValueZero
算法。
2. for...of
+ includes
实现
includes()
方法使用 sameValueZero
算法来确定是否找到给定元素。
3. reduce
+ includes
实现
通过 reduce
实现遍历,写法和 for
区别比较大
4. sort
+ forEach
实现(sort 并无意义,本质还是遍历)
该方法,是否使用 sort 并无区别,都要遍历所有。另注意 sort
会改变原数组,慎用(可使用副本)
sort()
方法用原地算法对数组的元素进行排序,并返回数组。默认排序顺序是先将元素转换为字符串,然后比较它们的UTF-16
代码单元值序列时构建的
就地算法是一种不使用辅助数据结构来转换输入的算法。
注意:sort()
默认排序时,需要调用 toString()
方法,在 null prototype
场景时就会报错
自 EcmaScript 2019 起,规范要求 Array.prototype.sort 为稳定排序。
5. 遍历 + hasOwnProperty
结合缓存实现(有限制)
此方案有限制,以下情况会异常
- 不能处理
Object.create(null)
, 报错VM49:4 Uncaught TypeError: Cannot convert object to primitive value
- 不能处理
Symbol()
,报错TypeError: Cannot convert a Symbol value to a string
大多数 Javascript 对象的toString()
方法都继承自Object.prototype
。但是其中一些如 Object.create(null)
, Symbol()
具有 null prototype, not havetoString()
方法,因此 Javascript 将无法将这些对象转换为字符串原语。and can't convert object to primitive error will rise
.
6. 遍历 + Map
实现
利用 Map
缓存,实现 hashTable 去重
Map
键的相等(Key equality)是基于 sameValueZero 算法的(NaN
是与 NaN
相等的,其他的值同 ===
运算符)
异常处理
const map = new Map()
// 会报错 `Uncaught TypeError: Cannot convert object to primitive value`
map[Object.create(null)] = true
// 需改为
map.set(Object.create(null), true)
- MDN Map
示例
// 调用 toString 会报错
Object.create(null) + ''
// 等同于
Object.create(null).toString()
点我查看详细
// 1. Set
function unique1(arr) {
return [...new Set(arr)]
// return Array.from(new Set(arr))
}
// 2. for + indexOf, (foreach, filter 类似)
function unique2(arr) {
const result = []
for (let i = 0; i < arr.length; i++) {
if (result.indexOf(arr[i]) > -1) continue
result.push(arr[i])
}
return result
}
// 3. for...of + includes
function unique3(arr) {
const result = []
for (const item of arr) {
if (result.includes(item)) continue
result.push(item)
}
return result
}
// 4. reduce + includes
function unique4(arr) {
return arr.reduce(
(prev, cur) => (prev.includes(cur) ? prev : [...prev, cur]),
[]
)
// return arr.reduce((prev, cur) => prev.includes(cur) ? prev : prev.concat(cur), [])
// return arr.reduce((prev, cur) => prev.indexOf(cur) > -1 ? prev : prev.concat(cur), [])
}
// 废弃方案 5. sort + for
function unique5(arr) {
let result = []
let last
// 这里解构是为了不对原数组产生副作用
;[...arr]
// 默认将 key 转为字符串比较,会报错
.sort((a, b) => (a === b ? 0 : 1))
.forEach((item) => {
if (item != last) {
result.push(item)
last = item
}
})
return result
}
// 6. 遍历 + `hasOwnProperty` 实现
function unique6(arr) {
const obj = {}
return arr.filter((item) => {
return obj.hasOwnProperty(typeof item + item)
? false
: (obj[typeof item + item] = true)
})
}
// 7. 遍历 + `Map` 实现
// map 的 key, 不能为 Object.create(null);
function unique7(arr) {
const map = new Map() // 改为 Map
return arr.filter((item) => {
return map.has(item) ? false : !!map.set(item, true)
})
}
// testing
let name
let symbol = Symbol(1)
// prettier-ignore
let arr = [
+0, -0, 0, NaN, NaN,
1, 1, false, false,
'', '0', '0', '1','NaN',
undefined, name, null, null,
// symbol, symbol, Symbol(1), Symbol(2), Symbol(2),
// 引用类型,不重复
{}, {},
Object.create(null), Object.create(null),
{city: 'shanghai'}, {city: 'shanghai'}
]
console.log(unique1(arr))
console.log(unique2(arr))
console.log(unique3(arr))
console.log(unique4(arr))
console.log(unique5(arr))
console.log(unique6(arr))
console.log(unique7(arr))
// console.log(arr.sort((a, b) => a === b ? 0 : 1))
7. 扩展
- 数组对象去重(根据特定属性值判断去重)
new Set()
的时间复杂度- 本质是遍历一次,通过
SameValueZero
判断 O(n)
具有线性时间
- 本质是遍历一次,通过
简单对象数组去重(对象为 json 数据)
方案
- 先把每一项对象转为 json 字符串
- for 遍历去重,结合 cache 缓存,记住 index
- 将原数组对应位置去除
点我查看详细
// JSON 对象数组去重(只做第一层级)
// 1. 遍历
// 2. 转为 JSON 字符串(需要先按 key 排序)
// 3. 判断是否已缓存,是则直接跳过,否则就 push 到新数组里
function uniqueJsonArr(arr) {
const cache = {}
const result = []
for (let i = 0; i < arr.length; i++) {
let current = arr[i]
current = sortObj(current) // 补充排序操作
const jsonStr = JSON.stringify(current)
if (cache[jsonStr]) continue
cache[jsonStr] = true
result.push(arr[i])
}
return result
}
// testing
const jsonArr = [
{ name: 'red', age: 25 },
{ age: 25, name: 'red' },
{ name: 'green', age: 27 },
{ name: 'green', age: 27 },
{ name: 'blue', age: 28 },
{ name: 'blue', age: 28, phone: '123' },
]
console.log(uniqueJsonArr(jsonArr))
// 对象按 key 排序
function sortObj(obj) {
const keys = Object.keys(obj).sort()
const result = {}
while (keys.length) {
const key = keys.pop()
result[key] = obj[key]
}
return result
}
参考: