Serenader

Learning by sharing.

JavaScript 数组去重

故事的起因来自牛客网的一个测试,里面有一道数组去重的题,题目如下:

为 Array 对象添加一个去除重复项的方法
输入例子:
[false, true, undefined, null, NaN, 0, 1, {}, {}, 'a', 'a', NaN].uniq()

输出例子:
[false, true, undefined, null, NaN, 0, 1, {}, {}, 'a']

之前刚好碰到过数组的去重这个问题,于是按照之前的印象,想都没想就写下:

Array.prototype.uniq = function () {
	var map = {};
	return this.filter(function (item) {
		if (map[item]) {
			return false;
		} else {
			map[item] = true;
			return true;
		}
	});
};

写完之后鸡冻地点了提交运行,脸上挂满了微笑。过了几秒,页面提示提交的代码未通过测试用例。。唔。。。这不科学,我的代码居然不通过!这怎么可能!!!肯定是手抖打错字母了!!于是检查了几遍,在Chrome控制台测了几遍,然后再提交。结果还是一样。难道是写法不对?赶紧换个姿势写,再提交,结果特么的还是不通过。。好吧,我开始怀疑这网站是不是有bug了。。。不过想想,怎么别人就能通过我就老是过不去呢……肯定是自己代码有问题,再检查一下代码!

后来才发现,上面这段代码无法去重这样的数组:['1', 1] 。好吧,被自己的愚蠢给吓到了。突然间觉得自己 too young too simple, sometimes naive 啊。。

于是乎,赶紧Google一番,涨涨姿势压压惊。果然,皇天不负有心人呐,这不,StackOverflow里面就有一个 满分的答案,看完之后觉得很有必要做个笔记,于是就有了这篇文章。嗯,废话到此结束。


利用 filter 函数和 indexOf 函数

当一个数组里面有重复的元素时,那么为重复的元素调用 indexOf 方法得到的位置不总是正确的,因此可以根据该方法来去重。

Array.prototype.uniq = function () {
	var _this = this;
	return _this.filter(function (item, pos) {
		// 当元素实际位置与indexOf方法返回的位置一致时,则该元素不是重复的元素。
		// 反之,即为重复的元素,去除之。
		return _this.indexOf(item) == pos;
	});
};

优点:简洁明了。

缺点:效率低,而且无法去重 NaN{}

利用 hash 表

利用对象的属性名不能重复这一特性,即可进行筛选。这种方法也就是开篇所提到的代码方法。相对而言,下面这段代码更加简练优美。

Array.prototype.uniq = function () {
	var map = {};
	return this.filter(function (item) {
		return map.hasOwnProperty(item) ? false : (map[item] = true);
	});
};

优点: 速度较第一种快。

缺点: 无法区分 '1' 和 1 ,以及对象 {foo: 1} 和 {foo: 2}。

进一步优化 hash 表,对每个元素进行类型判断

在上一个方法中,导致该方法的缺点的根本原因是因为,在执行 map[item] = true 时,会对 item 进行一次 toString 转换,因此才会导致无法去重 ['1', 1],因为此时均转换为 '1' 了。对于对象的话,则是转换成 '[object Object]' 了。那么,如果我们在一开始时即把他们的类型检测出来,再利用 hash 表方法,那么即可以达到去重的目的。

Array.prototype.uniq = function () {
	var prims = {boolean: {}, number: {}, string: {}};
	var obj = [];
	return this.filter(function (item) {
		var type = typeof item;
		if (type in prims) {
			return prims[type].hasOwnProperty(item) ? false : (prims[type][item] = true);
		} else {
			return obj.indexOf(item) != -1 ? false : (obj.push(item));
		}
	});
};

等等,为啥 prims 里面每个属性都是一个对象?不能用数组吗?像是这样:

Array.prototype.uniq = function () {
	var prims = {boolean: [], number: [], string: []};
	var obj = [];
	return this.filter(function (item) {var type = typeof item;
    	if (type in prims) {
		    return prims[type].indexOf(item) != -1 ? false : (prims[type].push(item));
	    } else {
	    return obj.indexOf(item) != -1 ? false : (obj.push(item));
	    }
    });
};

我们先来看下面一段代码:

var arr = [undefined, null, NaN, {}];
arr.indexOf(undefined); // 0
arr.indexOf(null); // 1
arr.indexOf(NaN); // -1
arr.indexOf({}); // -1

可见,indexOf 方法对于 NaN 和空对象而言总是返回 -1,也因此,如果 prims 的属性是数组的话,那么 prims.number 数组里面则可能会出现多个 NaN,从而无法去重 NaN
根本原因在于

undefined === undefined // true
null === null //true
NaN === NaN // false
typeof NaN === 'number'
({}) === ({}) // false

值得一提的是,这种方法去重能够通过牛客网的那道去重的题目。

优点: 比较理想的去重。

缺点: 无法去除两个相同的对象,比如 {} 和 {}。这是因为 ({}) === ({}) // false 这个原因。具体可以看我之前写的博文 == VS === ? The Evil or the Angel ?

继续修改 hash 表,使得完美去除相同的对象

Array.prototype.uniq = function () {
	var map = {};
	return this.filter(function (item) {
		var key = typeof item + item;
		return map.hasOwnProperty(key) ? false : (map[key] = true);
	});
};

优点: 速度快,效果好。

缺点: 好像木有?

另一个思路,使用 JSON.stringify 将每个元素转化为字符串,再用 hash 表去重:

Array.prototype.uniq = function () {
	var map = {};
	return this.filter(function (item) {
		var key = JSON.stringify(item);
		return map.hasOwnProperty(key) ? false : (map[key] = true);
	});
};

不过上面的方法无法去重 ['1', 1] 这样的数组,要达到去重这种数组的话,可以结合上面那一种方法,先判断元素类型,再进行检查是否重复。

对于数组只包含基本类型值时,可以先排序,再去重

Array.prototype.uniq = function () {
	var _this = this;
	return _this.sort().filter(function (item, pos) {
		return !pos || item != _this[pos - 1];
	});
};

其原理是排序后的数组中,依次比较前后两个元素的值即可知道是否有重复。
优点: 更快。

缺点: 只能对基本类型值进行排序,而对对象无效,因为对于 sort 函数而言对象都是一致的。


Reference

Comments is loading...

Comments is loading...