本文给大家汇总介绍了 javascript 中数组去重的 4 种方法, 分别是循环匹配去重, JSON 去重 / 对象去重 / 字典去重, 队列递归去重, INDEXOF 去重方式,非常的细致全面,有需要的小伙伴可以参考下。
Javascript 是一种由 Netscape 的 LiveScript 发展而来的原型化继承的基于对象的动态类型的区分大小写的客户端脚本语言,主要目的是为了解决服务器端语言,比如 Perl,遗留的速度问题,为客户提供更流畅的浏览效果。
前言
最近为了换工作,准备下面试,开始回顾复习 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;
- }
- }
来源: http://www.phperz.com/article/17/0302/266799.html