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

这是我参与更文挑战的第3天，活动详情查看： 更文挑战

[重学JavaScript系列文章连载中…]

场景：

存在一组数组：[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种算法。