LouieLiu

关于数组去重

发表于 | | 阅读次数

做练习的时候发现这样一道题

Description:

Your goal in this kata is to implement an difference function, which subtracts one list from another.It should remove all values from list a, which are present in list b.If a value is present in b, all of its occurrences must be removed from the other:

1
2
3
4
5
6
difference([1,2],[1]) == [2]
difference([1,2,2,2,3],[2]) == [1,3]
difference([1,2,2,3,3,4],[3]) == [1,2,4]
function array_diff(a, b) {
  //your code
}

  这道题本来没什么好说的就是除去第一个数组中所有包含的第二个参数中的元素 重点是最后一步的数组去重 其中第一步很容易解决

1
2
3
function array_diff(a, b) {
  a = a.filter(function(x) { return b.indexOf(x); });
}

  通过第一步 可以很容易得到已经除去多余元素后的数组 接下来数组去重 才是要考虑的重点，关于去重
注：数组a为已滤除多余元素的数组!!!

方法一

最简单的思路就是遍历得到的数组 然后新创建一个数组arr 通过比较遍历arr次数和arr的length来判断是否有相重元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function arr_unique(a) {
 var arr =[],
	 i,j,
	 len_j = arr.length,
	 len = a.length;
 for(i = 0;i<len;i++){
	for(j = 0;j<len_j;i++){
		if(a[i] === arr[j]){
			break;
		}
	}
	//若j和arr.length 相等 则表示没有相重元素 把当前元素添加到arr中
	if(j === len_j){
		arr.push(a[i]);
	}
 }
 return arr;
}
arr_unique([1,1,3,3,4]); // [1,3,4]
arr_unique([1,1,3,3,"1",4]);// [1, "1", 3, 4]

或者

1
2
3
4
5
6
7
8
9
function arr_unique(a){
	a = a.filter(function(ele,index,array){
		return array.indexOf(ele) === index;
	})
	return a;
}
arr_unique([1,1,3,3,4]); // [1,3,4]
arr_unique([1,1,3,3,"1",4]);// [1, "1", 3, 4]

此方法的时间复杂度为O(n²);

方法二

若不考虑数组输出顺序 可以使用sort()先排序后过滤的方法；使用sort()排序后数组中相同元素会在相邻位置只需要比较相邻位置的值是否相等就可以做出判断 大致实现方法如下:

1
2
3
4
5
6
7
8
9
function arr_unique(a){
	a = a.sort().filter(function(ele,index,array){
		return ele!==array[index - 1];
	});
	return a;
}
arr_unique([1,1,3,3,4]); // [1,3,4]
arr_unique([1,1,3,3,"1",4]);// [1, "1", 3, 4]

方法三

用JavaScript中的 Object 对象来当做哈希表 利用key来筛选(只能处理Number类型)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function arr_unique(a){
	var hash = {};
	var data = [];
	for(var i = 0; i<a.length;i++){
		if(!hash[a[i]]){
			hash[a[i]]= true;
			data.push(a[i]);
		}
	}
	return data;
}
arr_unique([1,1,3,3,4]); // [1,3,4]
arr_unique([1,1,3,3,"1",4]); // [1,3,4]

方法四

方法三针对数组a中无其他类型元素做出的处理 若数组中加入字符串等其他元素 则会出现问题 因为Object的key都是String类型所以无法区别出形如2，”2”这样的值 使用上述方法会忽略掉”2”通过改进方法三将每个值得类型也添加到key中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function arr_unique(a){
	var hash = {};
	var data = [];
	for(var i = 0; i<a.length;i++){
		var its = a[i];
		var key = its+typeof(its);
		if(!hash[key]){
			hash[key]= true;
			data.push(its);
		}
	}
	return data;
}
arr_unique([1,1,3,3,4]); // [1,3,4]
arr_unique([1,1,3,3,"1",4]); // [1,3,4]

方法五

利用ES6的Set与Array.from()方法

1
2
3
4
5
6
function arr_unique(a){
	 return Array.from(new Set(a));
}
arr_unique([1,1,3,3,4]); // [1,3,4]
arr_unique([1,1,3,3,"1",4]);// [1, "1", 3, 4]