【经典面试题】JavaScript数组去重
本文由 小茗同学 发表于 2016-09-28 浏览(1275)
最后修改 2016-10-23 标签:javascript 数组 去重 unique array

题目

已知有如下一个数组,要求实现一个去重方法:

var arr = ['aa', 'bb', 'cc', '', 1, 0, '1', 1, 'bb', null, undefined, null];

既然是面试题,肯定要考虑兼容性和效率。

几种实现

第一种实现

这是最容易想到的方法:

function unique1(array)
{
	var result = [];
	for(var i=0; i<array.length; i++)
	{
		if(result.indexOf(array[i]) < 0) result.push(array[i]);
	}
	return result;
}
var arr = ['aa', 'bb', 'cc', '', 1, 0, '1', 1, 'bb', null, undefined, null];
console.log(unique1(arr));

这种方法有2个缺点,一是效率问题,因为加上indexOf相当于是2重循环,二是indexOf的兼容性问题。

第二种实现

遍历数组所有元素,如果发现其indexOf值等于遍历的索引,则将其放到一个新数组去,这种方法比第一种方法效率还要差,我估计一般都不会想到这个方法:

function unique2(array)
{
	var result = [array[0]];
	for(var i=1; i<array.length; i++)
	{
		if(array.indexOf(array[i]) == i) result.push(array[i]);
	}
	return result;
}
var arr = ['aa', 'bb', 'cc', '', 1, 0, '1', 1, 'bb', null, undefined, null];
console.log(unique2(arr));

第三种实现

function unique3(array)
{
	var result = [];
	var hash = {};
	for(var i=0; i<array.length; i++)
	{
		var key = (typeof array[i]) + array[i];
		if(!hash[key])
		{
			result.push(array[i]);
			hash[key] = true;
		}
	}
	return result;
}
var arr = ['aa', 'bb', 'cc', '', 1, 0, '1', 1, 'bb', null, undefined, null];
console.log(unique3(arr));

这种实现方法中规中矩,不算最好也不算最差。

以上方法中之所以给key添加了类型前缀,是因为要区分'1'1

第四种实现

function unique4(array)
{
	return Array.from(new Set(array));
}
var arr = ['aa', 'bb', 'cc', '', 1, 0, '1', 1, 'bb', null, undefined, null];
console.log(unique4(arr));

这种方法是评论里网友提到的,使用了ES6种的Set,虽然效率很高,但是兼容性大大滴有问题。

第五种实现

//TODO

速度比较

测试50万长度的数组,环境为Win10+Chrome50.0

var testArray = [];
for(var i=0; i<500000; i++)
{
	testArray.push(parseInt(Math.random()*100));
}
function test(fn, name)
{
	console.time(name);
	fn(testArray);
	console.timeEnd(name);
}
test(unique1, '第1种实现');
test(unique2, '第2种实现');
test(unique3, '第3种实现');
test(unique4, '第4种实现');

结果比较惊讶:

第1种实现: 43.867ms
第2种实现: 234.370ms
第3种实现: 48.405ms
第4种实现: 31.978ms

第1种实现竟然比第3种略快一些,这个不知为何,可能是现代浏览器内部做了啥优化吧。