前言
最近为了换工作,准备下面试,开始回顾复习JavaScript相关的知识,昨天下午想到了数组去重的相关方法,干脆整理出几篇JavaScript算法文章,以备后用,此系列文章不定篇数,不定时间,想到哪写到哪,不保证正确性,不保证高效率,只是谈谈个人理解,如有错误,请诸位斧正。
关于去重
数组去重是一个比较常见的算法考察点,实现去重的方式无外乎通过唯一性和非唯一性。简单来讲就是挑出唯一的或者删除不唯一的。以下所有算法都是我自己瞎命名的,请无视之。
循环匹配去重
顾名思义,就是把数组中的每一个元素都和存放元素的数组对比,遇到不重复的元素,放入新数组中,直至循环结束,由于匹配也有循环,也可以称为双循环匹配去重,这也是大家都能想到的最简单的方式。
实现代码:
var arr=[1,3,4,56,3,7,9,7]; var result=[]; //匹配 function isMatch(array,n){ for(var i=0;i<array.length;i++){ if(array[i]==n){ return true; } } return false; }; //验证所有元素 function unqiue(array){ for(var i=0;i<array.length;i++){ if(!isMatch(result,array[i])){ result.push(array[i]); } } return result; }; console.log(unqiue(arr));
注意:上面方法有一个bug,当存在数字和数字形式的字符串的时候,没有区分出数字和数字字符串。因为在匹配函数isMatch()里用的是双等“==”,没有验证元素类型,实际应该使用全等“===”。
修改后的代码如下:
var arr=[1,3,4,56,3,'1',7,9,7]; var result=[]; //匹配 function isMatch(array,n){ for(var i=0;i<array.length;i++){ if(array[i]===n){ return true; } } return false; }; //验证所有元素 function unqiue(array){ for(var i=0;i<array.length;i++){ if(!isMatch(result,array[i])){ result.push(array[i]); } } return result; }; console.log(unqiue(arr));
算法优缺点:
优点:
实现简单,思路直观
缺点:
效率低下
JSON去重/对象去重/字典去重
JSON去重,简单来讲就是利用Object对象key的唯一性,将数组的元素转换为JSON或者说对象的key值。JSON的value存储数组的索引index,然后对JSON对象进行for in循环,存储到新数组中。
Array、JSON、{}都是Object,所以采用任意一种都可以实现此算法。
实现代码:
Array方式:
var arr=[1,3,4,56,3,'1',7,9,7]; function unqiue(array){ var cache=[]; var result=[]; //将数组元素转为对象的key for(var i=0;i<array.length;i++){ cache[array[i]]=i; }; //存储key(实际的数组元素) for(key in cache){ result.push(key); }; return result; } console.log(unqiue(arr));
JSON方式:
var arr=[1,3,4,56,3,'1',7,9,7]; function unqiue(array){ var cache={}; var result=[]; //将数组元素转为对象的key for(var i=0;i<array.length;i++){ cache[array[i]]=i; }; //存储key(实际的数组元素) for(key in cache){ result.push(key); }; return result; } console.log(unqiue(arr));
Object方式:
var arr=[1,3,4,56,3,'1',7,9,7]; function unqiue(array){ var cache=new Object(); var result=[]; //将数组元素转为对象的key for(var i=0;i<array.length;i++){ cache[array[i]]=i; }; //存储key(实际的数组元素) for(key in cache){ result.push(key); }; return result; } console.log(unqiue(arr));
算法优缺点:
优点:
简单
效率非常高
缺点:
1.改变了数组元素的类型()
2.有bug(无非区分数字和数字类型字符串)
队列递归去重
昨天晚上思忖良久想到用队列的方式,先将数组排序成升序或降序的队列,这样相同的元素就处在一个区域内,然后从队尾向前匹配,如果匹配成功,删除队尾,然后前一个元素再向其前面的匹配。整个匹配完成之后,剩下的元素就是去重过后的队列。
var arr=[6, 4, 6, 9, '6', 13, 56, 9, ,'11',1, 8, '7', 17, 5, 45, 3, 7]; function unqiue(array){ //排序数组,形成队列 array.sort(function(m,n){return m-n;}); ////排序后,队尾向前对比,如果相同,删除队尾,依次类推 function loop(Index){ if(Index>=1){ if(array[Index]===array[Index-1]){ arr.splice(Index,1); } loop(Index-1); } } loop(array.length-1); return array; } console.log(unqiue(arr));
算法优缺点:
优点:
效率较高
缺点:
效率不是最高
INDEXOF去重方式
判断浏览器是否支持indexOf ,indexOf 为ecmaScript5新方法 IE8以下(包括IE8, IE8只支持部分ecma5)不支持
if (!Array.prototype.indexOf){ // 新增indexOf方法 Array.prototype.indexOf = function(item){ var result = -1, a_item = null; if (this.length == 0){ return result; } for(var i = 0, len = this.length; i < len; i++){ a_item = this[i]; if (a_item === item){ result = i; break; } } return result; } }
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
更新日志
- 凤飞飞《我们的主题曲》飞跃制作[正版原抓WAV+CUE]
- 刘嘉亮《亮情歌2》[WAV+CUE][1G]
- 红馆40·谭咏麟《歌者恋歌浓情30年演唱会》3CD[低速原抓WAV+CUE][1.8G]
- 刘纬武《睡眠宝宝竖琴童谣 吉卜力工作室 白噪音安抚》[320K/MP3][193.25MB]
- 【轻音乐】曼托凡尼乐团《精选辑》2CD.1998[FLAC+CUE整轨]
- 邝美云《心中有爱》1989年香港DMIJP版1MTO东芝首版[WAV+CUE]
- 群星《情叹-发烧女声DSD》天籁女声发烧碟[WAV+CUE]
- 刘纬武《睡眠宝宝竖琴童谣 吉卜力工作室 白噪音安抚》[FLAC/分轨][748.03MB]
- 理想混蛋《Origin Sessions》[320K/MP3][37.47MB]
- 公馆青少年《我其实一点都不酷》[320K/MP3][78.78MB]
- 群星《情叹-发烧男声DSD》最值得珍藏的完美男声[WAV+CUE]
- 群星《国韵飘香·贵妃醉酒HQCD黑胶王》2CD[WAV]
- 卫兰《DAUGHTER》【低速原抓WAV+CUE】
- 公馆青少年《我其实一点都不酷》[FLAC/分轨][398.22MB]
- ZWEI《迟暮的花 (Explicit)》[320K/MP3][57.16MB]