摘要:缺点不兼容以下浏览器七高阶函数方法用来判断一个数组是否包含一个指定的值,根据情况,如果包含则返回,否则返回。方法六高阶函数优点高阶函数的高级用法。
一、前言
数组去重是一个老生常谈的问题,但是有时候会弹出点其他东西。
二、双重循环这个方法是最常见的,最原始的方法。
</>复制代码
// 方法一:双重循环
var array = [1,1,"1","2","1",1,2]
function unique(arr){
// res 存结果
var res = [];
for(var i = 0, length = arr.length; i < length; i++){
for(var j = 0, length2 = res.length; j < length2; j++){
if(arr[i] === res[j]){
break;
}
}
if(j == length2){
res.push(arr[i])
}
}
return res;
}
unique(array); //[1, "1", "2", 2]
思路:双层循环方法,使用的是循环嵌套,外层是arr,里层是res,如果arr[i]的值等于res[j]的值,则跳出当前循环,如果都不等于,说明元素唯一,这时候j的值等于res的长度,根据这个判断,将值添加res中。
优点:兼容性好
缺点:时间复杂度o(n2)
三、indexOf方法思路:使用indexOf简化内层循环。
</>复制代码
// 方法二:indexOf简化内层循环
var array = [1,1,"1","2","1",1,2]
function unique(arr){
// res 存结果
var res = [];
for(var i = 0, length = arr.length; i < length; i++){
var current = arr[i];
if(res.indexOf(current) === -1){
res.push(current);
}
}
return res;
}
unique(array); //[1, "1", "2", 2]
优点:时间复杂度降低
缺点:有的浏览器不支持indexOf方法,时间复杂度o(n2)
四、排序后去重思路:使用快排sort将数组排序,这样相同的值会被排在一起,只需要判断当前元素与上一个元素是否相同,相同说明重复,不同就添加进res中。
</>复制代码
// 方法三:排序后去重
var array = [1,1,"1","2","1",1,2]
function unique(arr){
// res 存结果
var res = [];
var sortedArray = arr.concat().sort();
console.log(sortedArray, "-=-=-=-=-=-=")
var current;
for(var i = 0, length = sortedArray.length; i < length; i++){
// 如果是第一个元素 或者是相邻元素不相同
if(!i || current !== sortedArray[i]){
res.push(sortedArray[i]);
}
current = sortedArray[i];
}
return res;
}
unique(array); //[1, "1", 1, "2", 2]
优点:已经排好序的数组去重,这种方法效率高于使用 indexOf,时间复杂度o(n)
缺点:已经修改数组的顺序,同时存在去重不彻底
注意:sort函数默认排序是 Unicode,srot方法默认可是能给字母实现排序。突然发现了sort在排序的时候存在一个隐式转换,会把要排序的对象转换成字符串,sort排序的时候1和"1"是相同的,然后根据unicode比较大小,所以出现了[1, "1", 1, "2", 2]这种情况。
注意:数组进行了 array.concat()操作之后,其实是复制出来一份原有的数组,复制出来的新数组不会影响到原有数组。
五、使用ES5的filter思路:使用filter简化外层循环
1、使用indexOf简化内层循环</>复制代码
// 方法四:filter + indexOf
var array = [1,1,"1","2","1",1,2]
function unique(arr){
// res 存结果
var res = arr.filter(function(item, index, arr){
return arr.indexOf(item) === index;
})
return res;
}
unique(array); //[1, "1", "2", 2]
2、排序去重的方法
</>复制代码
// 方法四:filter + sort
var array = [1,1,"1","2","1",1,2]
function unique(arr){
// res 存结果
var res = arr.concat().sort().filter(function(item, index, arr){
return !index || item !==arr[index -1]
})
return res;
}
unique(array); //[1, "1", 1, "2", 2]
上面已经讲到了sort排序时候存在一个隐式转换。
优点:很简洁,思维也比较巧妙,直观易懂,使用filter简化外层循环
缺点:不支持 IE9 以下的浏览器,时间复杂度o(n*2)
六、Object键值对的问题思路:利用一个空的Object对象,把数组的值存成Object的key,比如就是Object[value] = true;循环判断的时候,如果Object[value]存在,说明这个值重复了。
</>复制代码
// 方法五:Object键值对
var array = [1,1,"1","2","1",1,2]
function unique(arr){
// obj 存对象
var obj= {};
var res = arr.filter(function(item, index, arr){
if(obj.hasOwnProperty(item)) return false;
else {
return obj[item] = true;
}
})
return res;
}
unique(array); //[1, "2"]
然后我们发现1和"1"是不同的,但是这种方法会判断为是同一个值,因为键值对中只能是字符串,会进行一个隐式转换。和sort排序时候的转换是一样的,可以通过typeof item+ item,拼成字符串作为key的值避免这个问题
</>复制代码
// 优化
function unique(arr){
// obj 存对象
var obj= {};
var res = arr.filter(function(item, index, arr){
if(obj.hasOwnProperty(typeof item + item)) return false;
else {
return obj[typeof item + item] = true;
}
})
return res;
}
unique(array); //[1, "1", "2", 2]
优点:hasOwnProperty是对象的属性存在性检查方法。对象的属性可以基于hash表实现,因此对属性的方法的时间复杂度达到O(1);filter是数组迭代的方法,内部是一个for循环,复杂度O(n)。总的时间复杂度O(n)。
缺点:不兼容IE9以下浏览器
七、reduce高阶函数includes() 方法用来判断一个数组是否包含一个指定的值,根据情况,如果包含则返回 true,否则返回false。
</>复制代码
// 方法六:reduce高阶函数
var array = [1,1,"1","2","1",1,2]
function unique(arr){
let newArr = arr.reduce((pre,cur)=>{
if(!pre.includes(cur)){
return pre.concat(cur)
}else{
return pre
}
},[]);
return newArr;
}
console.log(unique(array));// [1, "1", "2", 2]
优点:高阶函数的高级用法。
缺点:兼容性问题,对象数组不能使用includes方法来检测。includes区分大小写
八、ES6的Set数据结构只能说ES6标准越来越好,可以使用Set数据结构,ES6中提供了set数据结构,类似于数组,成员值都是唯一的,没有重复的。
</>复制代码
// 方法七:ES6的set
var array = [1,1,"1","2","1",1,2]
function unique(arr){
return Array.from(new Set(arr));
}
unique(array); //[1, "1", "2", 2]
还可以用扩展运算符...
</>复制代码
// 优化
var array = [1,1,"1","2","1",1,2]
function unique(arr){
return [...new Set(arr)];
}
unique(array); //[1, "1", "2", 2]
再写简单点
</>复制代码
// 再优化
var array = [1,1,"1","2","1",1,2]
const unique = arr => [...new Set(arr)];
unique(array); //[1, "1", "2", 2]
优点:ES6语法简单高效。
缺点:兼容性问题,加上使用babel编译不是问题。
九、ES6的Map数据结构</>复制代码
// 方法八:ES6的Map + filter
var array = [1,1,"1","2","1",1,2];
function unique(arr){
var current = new Map();
var res = arr.filter(function(item, index, arr){
if(current.has(item)){
return false;
}else{
return current.set(item, 1);
}
})
return res;
}
unique(array); //[1, "1", "2", 2]
思路:使用map的方法set和has,用has方法来判断是否存在这个key,如果没有值将map中存一个key-value。
注意:最新的ES6规范引入了新的数据类型Map,为了解决对象中的键只能是字符串的问题,其实其他基本数据类型是可以作为键的。
优点:ES6语法简单高效。
缺点:兼容性问题,加上使用babel编译不是问题。
十、特殊数据类型比较</>复制代码
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
看个栗子1
</>复制代码
var arr = [1, 2, NaN];
arr.indexOf(NaN); // -1
原因:indexOf底层还是使用 === 来进行判断的,因为NAN === NAN结果是false,使用indexOf还是查不到NAN这个元素。
再看个栗子2
</>复制代码
function unique(array) {
return Array.from(new Set(array));
}
console.log(unique([NaN, NaN])) // [NaN]
Set中,NAN === NAN是false,但是这两个元素是重复的
十一、后话在对数组去重的性能进行优化,然后想了半天也只写出来了Object键值对的性能,找不到其他既能判断引用类型,性能又稳定在n^2之内的方式?
自己回答一下:
目前时间复杂度到O(n)的方法:
(1)Object键值对,实质是hasOwnProperty的hash表。
(2)ES6的set,map的数据结构
(3)reduce高阶函数
【注:我是saucxs,也叫songEagle,松宝写代码,文章首发于sau交流学习社区(https://www.mwcxs.top),关注我们每天阅读更多精彩内容】
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/104888.html
摘要:写在前面专题系列是我写的第二个系列,第一个系列是深入系列。专题系列自月日发布第一篇文章,到月日发布最后一篇,感谢各位朋友的收藏点赞,鼓励指正。 写在前面 JavaScript 专题系列是我写的第二个系列,第一个系列是 JavaScript 深入系列。 JavaScript 专题系列共计 20 篇,主要研究日常开发中一些功能点的实现,比如防抖、节流、去重、类型判断、拷贝、最值、扁平、柯里...
摘要:种常用数组去重第一种两个循环思路新建一个为空的结果数组外层遍历原数组,内层循环遍历返回数组判断内层循环数组当前元素和外层数组元素的值是否相等,是退出内层循环经过第二部后,此时内层循环数组的索引值和返回数组的长度正好相等,外层数组元素也是唯一 8 种常用数组去重 第一种 【两个 for 循环】 思路: 新建一个为空的结果数组 外层 for 遍历原数组,内层循环遍历返回数组 判断内层循环...
摘要:设计模式是以面向对象编程为基础的,的面向对象编程和传统的的面向对象编程有些差别,这让我一开始接触的时候感到十分痛苦,但是这只能靠自己慢慢积累慢慢思考。想继续了解设计模式必须要先搞懂面向对象编程,否则只会让你自己更痛苦。 JavaScript 中的构造函数 学习总结。知识只有分享才有存在的意义。 是时候替换你的 for 循环大法了~ 《小分享》JavaScript中数组的那些迭代方法~ ...
摘要:专题系列共计篇,主要研究日常开发中一些功能点的实现,比如防抖节流去重类型判断拷贝最值扁平柯里递归乱序排序等,特点是研究专题之函数组合专题系列第十六篇,讲解函数组合,并且使用柯里化和函数组合实现模式需求我们需要写一个函数,输入,返回。 JavaScript 专题之从零实现 jQuery 的 extend JavaScritp 专题系列第七篇,讲解如何从零实现一个 jQuery 的 ext...
阅读 1556·2021-10-08 10:05
阅读 4266·2021-09-22 15:54
阅读 3178·2021-08-27 16:18
阅读 3174·2019-08-30 15:55
阅读 1547·2019-08-29 12:54
阅读 2826·2019-08-26 11:42
阅读 650·2019-08-26 11:39
阅读 2209·2019-08-26 10:11