js 实现数组去重怎么实现?
方法 1. 创建一个新的临时数组来保存数组中已有的元素
- var a = new Array(1,2,2,2,2,5,3,2,9,5,6,3);
- Array.prototype.unique1 = function(){
- var n = []; // 一个新的临时数组
- for(var i=0; i<this.length; i++){
- // 如果把当前数组的第 i 已经保存进了临时数组, 那么跳过
- if(n.indexOf(this[i]) == -1){
- n.push(this[i]);
- }
- }
- return n;
- }
- console.log(a.unique1());
方法 2. 使用哈希表存储已有的元素
- Array.prototype.unique2 = function(){
- var hash = {},
- n = []; //hash 作为哈希表, n 为临时数组
- for(var i=0; i<this.length; i++){
- if(!hash[this[i]]){ // 如果 hash 表中没有当前项
- hash[this[i]] = true; // 存入 hash 表
- n.push(this[i]); // 当前元素 push 到临时数组中
- }
- }
- return n;
- }
方法 3. 使用 indexOf 判断数组元素第一次出现的位置是否为当前位置
- Array.prototype.unique3 = function(){
- var n = [this[0]];
- for(var i=1; i<this.length; i++) // 从第二项开始遍历
- {
- // 如果当前数组元素在数组中出现的第一次的位置不是 i
- // 说明是重复元素
- if(this.indexOf(this[i]) == i){
- n.push(this[i]);
- }
- }
- return n;
- }
方法 4. 先排序再去重
- Array.prototype.unique4 = function(){
- this.sort(function(a, b){ return a - b;});
- var n = [this[0]];
- for(var i=1; i<this.length; i++){
- if(this[i] != this[i-1]){
- n.push(this[i]);
- }
- }
- return n;
- }
第一种方法和第三种方法都使用了 indexOf(), 这个函数的执行机制也会遍历数组
第二种方法使用了一个哈希表, 是最快的.
第三种方法也有一个排序的复杂度的计算.
然后做了个测试, 随机生成 100 万个 0-1000 的数组结果如下:
来源: http://www.qdfuns.com/article/42711/90128b94dce301be205c01095dcbfd39.html