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

关注

发布于: 2020 年 12 月 29 日

数组相关文章：
数组去重的 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

原文链接:【http://xie.infoq.cn/article/be3a0d53c5ba9d46f4cb044d6】。文章转载请联系作者。

梁龙先森

关注

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

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

发布

暂无评论