JavaScript 算法初探——数组去重

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

[otakustay]

咱们直接用 Map 类就好了嘛……

[sumhat]

谈到算法效率的时候，请给出时空复杂度。

[xqin]

我想说的是: 楼主居然分不清 `JSON` 和 `Object`, 以及居然不知道 `{}` 是 `new Object` 的缩写.
居然单独把 var cache = {} 做为 `JSON` 拿来讲.

[markowitz73]

如果不保证效率，那么算法有什么意义呢？

[holyghost]

咱们直接用 Set 类就好了嘛……

[ChiChou]

我也想吐槽 JSON 这个说法

[sampeng]

特意来登陆吐槽 JSON 的。。
用同样的时间做去重，用 map ，只是消耗现代机器无视的内存占用来去重。可以最少比你多写 3 个函数了。。。

[jsonline]

JSON 是哪四个单词的全称楼主

[learnshare]

JSON 是文件格式 /文本格式吧

`!cache[array[i]]` 不能用来判断 `value == false` 的情况

[daysv]

[ 1, 1, 'a', 'a' ].filter( (el, i, arr) => arr.indexOf(el) === i);

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

一般这样就好了吧，搞的长篇大论啊？？

[codespots]

统一回复下 JSON 的问题，这个确实是我失误没有说清楚，本来只是用比较通俗的说法来解释下{}去重的方式，本来想用字典吧，但是字典属于 python 的说法。所以就用了 json 来指代下，因为 json 的 key 也具有唯一性嘛，给各位道歉，至于{}和 new object 缩写我是知道的，以后不敢随便在 V2EX 上发文章了，太可怕了。

[codespots]

至于为什么不用 object 来指代，因为 json 格式比较易于理解，也容易让各位注意到实际上数组元素的类型已经被转换为了字符串，考虑不周，还望见谅。

[codespots]

@learnshare !cache[array[i]] 可以判断 value==false 的情况，这里的 false 只是做了新对象的 key ，实际是!cache[“ false ”]

@jsonline @sampeng @ChiChou @xqin JSON 是 JavaScript Object Notation 的缩写，抱歉啊，才疏学浅，表达不严谨，出了问题，请各位见谅。另外请教各位， V2EX 的帖子怎么删除啊，不敢再误导其他人。吾长见笑于大方之家

[zhujinliang]

不先 sort 然后依次比对么？

[v1024]

[...new Set([1, 1, 2, 2, 3, "a", "a"])]

搞定。。

[sagnitude]

for-in 很慢，数量级级别的慢（除了 IE ），不要用 for-in

[jianzong]

算法在哪？

[bumz]

ES6:
Array.from(new Set(array).values())

[yoa1q7y]

@westooy 这里都是大神，没把握最好不要发文章 （逃

[pupboss]

为什么 indexOf 的效率高，求证明，不是找茬
因为我只能想到这一种办法去重了
一直觉得效率很低下

[codespots]

@pupboss 是相对高，不是最高，最高是字典去重，用空间换时间， ES6 原生的方式我没测过

[murmur]

map 背后的实现应该是 hashmap 吧?

[trotyl]

@westooy 说的好像 indexOf 不是循环一样。。

[jarnanchen]

@daysv 说的方法就很好了啊

[xuwenmang]

@westooy 别跟网友计较，网友是什么，你说 xx 地方地政了，他们有一堆在下面讨论错别字的。

另外别发表文章到这里，发个链接就行了。这里不适合。没有销户，删除的地方，不要发文章。

[WittBulter]

目前只有 Set 是 O(n)吧...

[keyanzhang]

const nums = [ 1, 2, 1, 3, 1, 2, 4 ];

const withoutDups = Array.from(new Set(nums));

[vagary]

@zhujinliang 鱼爆一地

[xunuoi]

调用数组自己的 sort 方法后再做队列排序， sort 本身已经增加了复杂度了，整体效率并不会高

[xqin]

@xuwenmang 这话你说的就不对了, 他不发出来, 他怎么知道自己的不足?
你为什么看到的只是别人在挑他的毛病?
别人能找出来原因, 这只能说明他做的还不够, 自己还有不足的地方,
还需要学习. 这是在帮助他进步 好不好?
@westooy

[codespots]

感谢各位，我确实有很多不足，谢谢各位，我会努力的，年轻人还是要提高自己的姿势水平！

[Jaylee]

23333 年轻人还是要多提高自己的姿势水平再来写文章啊

[neoblackcap]

文章其实还好，但是觉得没有深入到根基，其实去重算法我觉得基本上就是基于 hash 的，还有神奇的 bloom-filter,当然也有简单暴力算法。
还有就是改变数据类型这个我觉得不是事吧，你在暴露的接口那里，再转换回去就好了嘛。你算法内部的数据结构怎么会是一个问题呢？关键是你要给出对应的时空复杂度，那才有讨论算法的价值。

[tedzhou]

就问一句 indexOf 的时间复杂度是多少？
还有 lz 列的 n 种写法其实是等效的。。