JavaScript系列--八种【数组去重】方法的总结
栏目: JavaScript · 发布时间: 5年前
内容简介:数组去重是一个老生常谈的问题,但是有时候会弹出点其他东西。这个方法是最常见的,最原始的方法。思路:双层循环方法,使用的是循环嵌套,外层是arr,里层是res,如果arr[i]的值等于res[j]的值,则跳出当前循环,如果都不等于,说明元素唯一,这时候j的值等于res的长度,根据这个判断,将值添加res中。
一、前言
数组去重是一个老生常谈的问题,但是有时候会弹出点其他东西。
二、双重循环
这个方法是最常见的,最原始的方法。
// 方法一:双重循环 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 ),关注我们每天阅读更多精彩内容】
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
精通Java并发编程(第2版)
[西] 哈维尔·费尔南德斯·冈萨雷斯 / 唐富年 / 人民邮电出版社 / 2018-10 / 89.00元
Java 提供了一套非常强大的并发API,可以轻松实现任何类型的并发应用程序。本书讲述Java 并发API 最重要的元素,包括执行器框架、Phaser 类、Fork/Join 框架、流API、并发数据结构、同步机制,并展示如何在实际开发中使用它们。此外,本书还介绍了设计并发应用程序的方法论、设计模式、实现良好并发应用程序的提示和技巧、测试并发应用程序的工具和方法,以及如何使用面向Java 虚拟机的......一起来看看 《精通Java并发编程(第2版)》 这本书的介绍吧!