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 数组去重的方式基本就总结到这里了，欢迎在评论里指出错误和贡献其他方法。

6535 次点击
所在节点    JavaScript
34 条回复
codespots
2016-03-07 21:07:08 +08:00
@pupboss 是相对高，不是最高，最高是字典去重，用空间换时间， ES6 原生的方式我没测过
murmur
2016-03-07 21:20:01 +08:00
map 背后的实现应该是 hashmap 吧?
trotyl
2016-03-07 21:26:58 +08:00
@westooy 说的好像 indexOf 不是循环一样。。
jarnanchen
2016-03-07 21:43:19 +08:00
@daysv 说的方法就很好了啊
xuwenmang
2016-03-07 21:45:54 +08:00
@westooy 别跟网友计较，网友是什么，你说 xx 地方地政了，他们有一堆在下面讨论错别字的。

另外别发表文章到这里，发个链接就行了。这里不适合。没有销户，删除的地方，不要发文章。
WittBulter
2016-03-08 04:04:44 +08:00
目前只有 Set 是 O(n)吧...
keyanzhang
2016-03-08 08:56:42 +08:00
const nums = [ 1, 2, 1, 3, 1, 2, 4 ];

const withoutDups = Array.from(new Set(nums));
vagary
2016-03-08 09:09:47 +08:00
@zhujinliang 鱼爆一地
xunuoi
2016-03-08 09:46:54 +08:00
调用数组自己的 sort 方法后再做队列排序， sort 本身已经增加了复杂度了，整体效率并不会高
O3YwA1ENkb7i35XJ
2016-03-08 11:00:14 +08:00
@xuwenmang 这话你说的就不对了, 他不发出来, 他怎么知道自己的不足?
你为什么看到的只是别人在挑他的毛病?
别人能找出来原因, 这只能说明他做的还不够, 自己还有不足的地方,
还需要学习. 这是在帮助他进步 好不好?
@westooy
codespots
2016-03-08 11:14:05 +08:00
感谢各位，我确实有很多不足，谢谢各位，我会努力的，年轻人还是要提高自己的姿势水平！
Jaylee
2016-03-08 11:44:17 +08:00
23333 年轻人还是要多提高自己的姿势水平再来写文章啊
neoblackcap
2016-03-08 15:54:22 +08:00
文章其实还好，但是觉得没有深入到根基，其实去重算法我觉得基本上就是基于 hash 的，还有神奇的 bloom-filter,当然也有简单暴力算法。
还有就是改变数据类型这个我觉得不是事吧，你在暴露的接口那里，再转换回去就好了嘛。你算法内部的数据结构怎么会是一个问题呢？关键是你要给出对应的时空复杂度，那才有讨论算法的价值。
tedzhou
2016-03-08 16:00:11 +08:00
就问一句 indexOf 的时间复杂度是多少？
还有 lz 列的 n 种写法其实是等效的。。

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

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

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

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

© 2021 V2EX