重学 JS | 数组去重的 7 种算法

用户头像
梁龙先森
关注
发布于: 2020 年 12 月 29 日
重学JS | 数组去重的7种算法

数组相关文章:

数组去重的 7 种算法

找出数组中出现次数最多元素的 4 种算法

数组遍历的 7 种方法及兼容性处理 (polyfill)

场景:

存在一组数组:[1,2,1,2,3,4,3],通过算法去重数组内的重复元素,最终得到数组:[1,2,3,4]

1. 遍历数组

思路:函数内部新建一个数组,对传入的数组进行遍历。若遍历的值不在新数组中,则添加进去,否则不做处理。

function unique(array){
let result = []
for(let i=0;i<array.length;i++){
if(result.indexOf(array[i])===-1){ // 数值不存在新数组
result.push(array[i])
}
}
return result
}
unique([1,2,1,2]) // [1,2]

2. 利用对象键值对

思路:新建一个js对象以及一个新的数组,判断当前遍历的值是否为js对象的键。是,表示该元素已出现过,不做处理;不是,表示该元素是第一次出现,则给js对象插入该键,同时插入新的数组。

function unique(arrays){
let obj = {}, result = [], val, type;
for(let i=0;i<arrays.length;i++){
val = arrays[i]
// 相同数值的Number类型 和 String类型,作为对象的key,返回值是一样的,最终都转为string类型查找
type = typeof val
if(!obj[val]){
obj[val] = [type]
result.push(val)
}else if(obj[val].indexOf(type)===-1){ //
obj[val].push(type)
result.push(val)
}
}
return result
}
unique(['1',1,1,2,3,2,3]) // ['1',1,2,3]

3. 先排序,再去重

思路:借助原生的sort()函数对数组进行排序,然后对排序后的数组进行相邻元素的去重,将去重后的元素添加到新的数组中,返回新数组。

function unique(arrays){
let result = [arrays[0]]
arrays.sort((a,b)=>a-b)
for(let i=0;i<arrays.length;i++){
if(arrays[i]!==result[result.length-1]){
result.push(arrays[i])
}
}
return result
}
unique([1,4,5,7,4]) // [1,4,5,7]

4. 优先遍历数组

思路:利用双层循环,分别指定循环的索引i与j,j的初始值为i+1。在每层循环中,比较索引i和j的值是否相等,相等则表示数组中出现相同值,则需要更新索引i与j,再对新索引的值进行比较。循环结束后会得到一个索引值i,表示的右侧没有出现相同的值,将其push到结果数组。

function unique(arrays){
let result = []
for(let i=0,l=arrays.length;i<arrays.length;i++){
for(let j=i+1;j<l;j++){
if(arrays[i]===arrays[j]){
j = ++i
}
}
result.push(arrays[i])
}
return result
}

5. 基于reduce()函数

思路:类似于算法2,借助一个key-value对象,在reduce()函数的循环中判断key是否重复。

function unique(arrays){
let obj = {},type;
return arrays.reduce(function(preVal,curVal){
type = typeof curVal
if(!obj[curVal]){
obj[curVal] = [type]
preVal.push(curVal)
}else if(obj[curVal].indexOf(type)<0){
obj[curVal].push(type)
preVal.push(curVal)
}
return preVal
},[])
}
unique([1,2,3,1,2,3,'1']) //  [1, 2, 3, "1"]

6. 借助es6的Set数据结构

思路:Set数据结构,类似数组,但是它的成员都是唯一的。

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

7. 借助ES6的Map数据结构

思路:Map是一种基于key-value存储数据的结构,每个key只能对应唯一的value。并且Map的key会识别不同数据类型的数据,即1和"1"在Map中会作为不同的key处理。

function unique(arrays){
let map = new Map()
return arrays.filter(item=> !map.has(item) && map.set(item,1) )
}

8. 总结

至此我们总结了数组去重的7种算法。



发布于: 2020 年 12 月 29 日阅读数: 11
用户头像

梁龙先森

关注

寒江孤影,江湖故人,相逢何必曾相识。 2018.03.17 加入

1月的计划是:重学JS,点个关注,一起学习。

评论

发布
暂无评论
重学JS | 数组去重的7种算法