JavaScript 算法初探——数组去重

2016-03-07 16:50:43 +08:00
 codespots

本文原发布在 segmentfault.com https://segmentfault.com/a/1190000004548931 在学是作者，现在贴到 V2EX ，所以不存在侵权。

前言

最近为了换工作，准备下面试，开始回顾复习 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));

算法优缺点：

优点:

  1. 实现简单，思路直观

缺点：

  1. 效率低下

JSON 去重 /对象去重 /字典去重 1

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. 效率非常高

缺点:

1.改变了数组元素的类型（去重后的元素都为字符串类型）
2.无法区分数字和数值型字符串

JSON 去重 /对象去重 /字典去重 2

第 2 种方式和第 1 种方式在本质上没有太多区别，反而因为做了判断，效率降低了一点点。

实现代码

var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];
function unqiue(array){
    var cache={};
    var result=[];
    for(var i=0;i<array.length;i++){
        //如果 json 或者是或 hash 里没有
        if(!cache[array[i]]){
            result.push(array[i]);
            //设置当前结果为已存在
            cache[array[i]]=true;
        }
    }
    return result;
}

console.log(unqiue(arr));

为什么说第 2 种方式和第一种方式没有本质的区别呢？第 2 种方式有一个临时的 hash 表 cache ，存储了最终结果 result 中是否存在对应元素记录。如果 cache 中的记录不存在，说明该数组元素没有重复。第 1 种方式没有做判断，因为 json 数组，对象等，本质就可以看做是 hash ， cache[array[i]]中 array[i]相同的只会存在一个，所以不需要做判断。这也是第 1 种更快一点点的原因,虽然效率没有第 1 种那么高，但这种方式引入了一种解决第 1 种方式 bug 的潜在方案，在为 Array 添加去重方式的时候会提到这个方案。

算法优缺点：

优点：

  1. 效率很高

缺点:

  1. 无法区分数字和数值型字符串

队尾递归去重

昨天晚上思忖良久想到用队列的方式，先将数组排序成升序或降序的队列，这样相同的元素就处在一个区域内，然后从队尾向前匹配，如果匹配成功，删除队尾，然后前一个元素再向其前面的匹配。整个匹配完成之后，剩下的元素就是去重过后的队列。

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));

算法优缺点：

优点：

  1. 效率较高

缺点:

  1. 没有保留原数组的顺序

indexOf 去重 1

ECMAScript5 为数组添加了两个位置方法： indexOf()和 lastIndexOf()。如果查找不到相应的数组元素，返回-1 。所以可以使用 indexOf 方式来去重。

实现代码：

var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];

function unqiue(array){
    var result=[];
    for(var i=0;i<array.length;i++){
        if(result.indexOf(array[i])==-1){
            result.push(array[i]);
        }
    }

    return result;
}

console.log(unqiue(arr));

优点：

  1. 效率较高

缺点：
2. 不兼容低版本浏览器（ ECMAScript5 才支持 indexOf()和 lastIndexOf()方法）

indexOf 去重 2

从上面的 indexOf 去重扩展开来，如果用 indexOf 查找一个数组的元素的结果不是该数组元素的索引，那么可以认为这个数组出现过。所以这也可以用来实现数组去重。

var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];

function unqiue(array){
    var result=[];
    for(var i=0;i<array.length;i++){
        if(array.indexOf(array[i])==i){
            result.push(array[i]);
        }
    }

    return result;
}

console.log(unqiue(arr));

其实循环判断可以从第 1 项开始，因为第 0 项肯定不会重复。

优点：

  1. 效率较高

缺点：
2. 不兼容低版本浏览器（ ECMAScript5 才支持 indexOf()和 lastIndexOf()方法）

为 Array 对象添加去重方法的坑

以上总结了几种去重方法，我们来个小例子为 Array 对象添加去重，方便直接调用，实际情况下我们是不推荐修改 JavaScript 原生对象的，容易造成污染或者不可控的情况的发生。

以 JSON 去重 1 的方式为 Array 添加对象，我们选用了“ cache=[]”的那种，结果不小心踩到了大坑。
```
var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];

Array.prototype.unqiue=function(){
var cache=[];
var result=[];
for(var i=0;i<this.length;i++){
cache[this[i]]=i;
}

for(key in cache){
    result[cache[key]]=key;
}

return result;

}

console.log(arr.unqiue());
```

结果居然把 Array 本身的 unqiue 方法也当做数组的内容输出出来了。

再对比下使用 JSON 或者对象的方式的结果
```
var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];

Array.prototype.unqiue=function(){
var cache={};
var result=[];
for(var i=0;i<this.length;i++){
cache[this[i]]=i;
}

for(key in cache){
    result[cache[key]]=key;
}

return result;

}
console.log(arr.unqiue());
```

结果是正常的。

所以，我们在向 Array 对象添加去重方法时，不能使用[]的方式，要使用 JSON 或者空对象的方式，但是依然无法区分数值和数值型字符串。

JSON 去重 3

在 JSON 去重 2 我们判断的是 cache[array[i]]值是否为真。 cache[array[i]]这种实际是当做 cache 的自定义属性存储的， array[i]被转成了字符串形式，也同样存在无非区分数值和数值型字符串的情况，所以我们需要对 JSON 方式 2 进行改造。

代码如下:

var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];
function unqiue(array){
    var cache={};
    var result=[];
    for(var i=0;i<array.length;i++){
        var record=typeof(array[i])+array[i];
        //如果 json 或者是或 hash 里没有
        if(!cache[record]){
            result.push(array[i]);
            //设置当前结果为已存在
            cache[record]=true;
        }
    }
    return result;
}

console.log(unqiue(arr));

相比于 JSON 去重 2 ，我们对判断条件做了修改， cache[array[i]]存在数值和数值字符串时[array[i]]相同的情况，但是[typeof(array[i])+array[i]]却不存在这种情况，数值的 typeof 为 number ，数值字符串的 typeof 为 string ，区分开了这两种情况。

所以最终我们为 Array 对象添加的是这样的去重方法

var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];
Array.prototype.unqiue=function(){
    var cache={};
    var result=[];
    for(var i=0;i<this.length;i++){
        var record=typeof(this[i])+this[i];
        //如果 json 或者是或 hash 里没有
        if(!cache[record]){
            result.push(this[i]);
            //设置当前结果为已存在
            cache[record]=true;
        }
    }
    return result;
}


console.log(arr.unqiue());

补充队列去重方式

从网友哪里知道另外的两种队列方式，代码如下，原理和我写的队尾递归去重类似，代码如下：

队尾去重

var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];
function unqiue(array){
    var result=[];
    array.sort(function(m,n){return m-n});
    for(var i=0;i<array.length;i++){
        if(array[i]!==result[result.length-1]){
            result.push(array[i]);
        }
    }

    return result;
}

 console.log(unqiue(arr));

队首去重

var arr=[6, 4, 6, 9, '6', 13,56, 9,'11',1, 8, '7', 17, 5, 45, 3, 7];
 function unqiue(array){
    var result=[];
    array.sort(function(m,n){return n-m});
    for(var i=0;i<array.length;i++){
        if(array[i]!==result[0]){
            result.unshift(array[i]);
        }
    }

    return result;

 }
 console.log(unqiue(arr));

附言：

关于 JavaScript 数组去重的方式基本就总结到这里了，欢迎在评论里指出错误和贡献其他方法。

5847 次点击
所在节点    JavaScript
34 条回复
otakustay
2016-03-07 17:16:19 +08:00
咱们直接用 Map 类就好了嘛……
sumhat
2016-03-07 17:20:14 +08:00
谈到算法效率的时候，请给出时空复杂度。
xqin
2016-03-07 17:25:41 +08:00
我想说的是: 楼主居然分不清 `JSON` 和 `Object`, 以及居然不知道 `{}` 是 `new Object` 的缩写.
居然单独把 var cache = {} 做为 `JSON` 拿来讲.
markowitz73
2016-03-07 17:34:21 +08:00
如果不保证效率，那么算法有什么意义呢？
holyghost
2016-03-07 17:37:25 +08:00
咱们直接用 Set 类就好了嘛……
ChiChou
2016-03-07 17:46:22 +08:00
我也想吐槽 JSON 这个说法
sampeng
2016-03-07 17:55:29 +08:00
特意来登陆吐槽 JSON 的。。
用同样的时间做去重，用 map ，只是消耗现代机器无视的内存占用来去重。可以最少比你多写 3 个函数了。。。
jsonline
2016-03-07 18:03:54 +08:00
JSON 是哪四个单词的全称楼主
learnshare
2016-03-07 18:08:05 +08:00
JSON 是文件格式 /文本格式吧

`!cache[array[i]]` 不能用来判断 `value == false` 的情况
daysv
2016-03-07 18:11:12 +08:00
[ 1, 1, 'a', 'a' ].filter( (el, i, arr) => arr.indexOf(el) === i);

Array.from( new Set([ 1, 1, 'a', 'a' ]) );

一般这样就好了吧，搞的长篇大论啊？？
codespots
2016-03-07 18:30:07 +08:00
统一回复下 JSON 的问题，这个确实是我失误没有说清楚，本来只是用比较通俗的说法来解释下{}去重的方式，本来想用字典吧，但是字典属于 python 的说法。所以就用了 json 来指代下，因为 json 的 key 也具有唯一性嘛，给各位道歉，至于{}和 new object 缩写我是知道的，以后不敢随便在 V2EX 上发文章了，太可怕了。
codespots
2016-03-07 18:31:40 +08:00
至于为什么不用 object 来指代，因为 json 格式比较易于理解，也容易让各位注意到实际上数组元素的类型已经被转换为了字符串，考虑不周，还望见谅。
codespots
2016-03-07 18:38:16 +08:00
@learnshare !cache[array[i]] 可以判断 value==false 的情况，这里的 false 只是做了新对象的 key ，实际是!cache[“ false ”]

@jsonline @sampeng @ChiChou @xqin JSON 是 JavaScript Object Notation 的缩写，抱歉啊，才疏学浅，表达不严谨，出了问题，请各位见谅。另外请教各位， V2EX 的帖子怎么删除啊，不敢再误导其他人。吾长见笑于大方之家
zhujinliang
2016-03-07 19:00:07 +08:00
不先 sort 然后依次比对么？
v1024
2016-03-07 19:05:43 +08:00
[...new Set([1, 1, 2, 2, 3, "a", "a"])]

搞定。。
sagnitude
2016-03-07 19:16:37 +08:00
for-in 很慢，数量级级别的慢（除了 IE ），不要用 for-in
jianzong
2016-03-07 19:26:05 +08:00
算法在哪？
bumz
2016-03-07 19:32:44 +08:00
ES6:
Array.from(new Set(array).values())
yoa1q7y
2016-03-07 19:50:56 +08:00
@westooy 这里都是大神，没把握最好不要发文章 （逃
pupboss
2016-03-07 20:52:17 +08:00
为什么 indexOf 的效率高，求证明，不是找茬
因为我只能想到这一种办法去重了
一直觉得效率很低下

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/261720

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX