Js-数组交集

89 阅读 0 评论 59 点赞

我是靠谱客的博主香蕉火，最近开发中收集的这篇文章主要介绍Js-数组交集，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

github：https://github.com/Vinson7lhl/MyStudyCode/blob/master/blog/array_intersection.js

首先要有一个讨论前提

（1）数组只能是一维数组

（2）里面的元素也应当是基础类型，如Boolean、Number、String

那么首先举一个例子：

let ar1 = [3,5,6,1,1,2,2,5],
ar2 = [1,5,6,2,4,1,1]

如果用肉眼看很容易看到交集应该是[1,5,6,2,1]，注意，这是以ar2逐一匹配ar1得到的结果；可以看出来：两个数组的交集就是两个集合重复的元素，结果是完全有可能发生重复的，比如上面的结果有两个1。而且因为数组是有先后顺序的，所以用哪个数组去匹配对方可能结果是不同的。

我特意现在网上找了几个方法，举例说明

方法1：通过filter过滤器，和includes函数

ar1.filter(item => ar2.includes(item))

假设：

let ar1 = [1,2,1,1,3,5],
ar2 = [0,5,2,1,1];
let result = ar1.filter(item => ar2.includes(item))
console.log(result)

大家可以运行一下结果为：

[1,2,1,1,5]

但实际应该是：

[1,2,1,5]

为什么出现冗余呢？根本原因在于用ar2去判断是否包含ar1中每个元素时，一旦匹配，并不会删除原数组中已经匹配的元素，从而导致重复匹配；所以要想求得准确交集，就要保证每次匹配后不应该再检索已匹配项

比如我们希望的结果是这样产生的

let ar1 = [1,2,1,1,3,5],
ar2 = [0,5,2,1,1];
/*
假设遍历ar2并依次匹配ar1
第1次匹配：0 --- [1,2,1,1,3,5] ===> 没有匹配，新数组[5,2,1,1]
第2次匹配：5 --- [1,2,1,1,3,5] ===> 匹配，剔除后数组应该为：[2,1,1],[1,2,1,1,3]
结果为[5]
第3次匹配：2 --- [1,2,1,1,3] ===> 匹配，剔除后数组应该为：[1,1],[1,1,1,3]
结果为[5,2]
第4次匹配：1 --- [1,1,1,3] ===> 匹配，剔除后数组应该为：[1],[1,1,3]
结果为[5,2,1]
第5次匹配：1 --- [1,1,3] ===> 匹配，剔除后数组应该为：[],[1,3]
结果为[5,2,1,1]
*/

这里大家可以想一想为什么要遍历ar2呢？因为长度短，遍历次数较低。

最终代码如下：

var empty = []
function jiaoji(arr1,arr2) {
// 永远从短的数组进行遍历
if (arr1.length < arr2.length) {
for(let i = 0; i < arr1.length; i++) {
// 如果匹配上了
if(arr2.indexOf(arr1[i]) !== -1) {
let arr2_index = arr2.indexOf(arr1[i])
empty.push(arr1[i])
// 剔除长数组重复元素得到新元素
arr2.splice(arr2_index, 1)
}
// 无论匹配上都要剔除短数组当下元素
arr1.splice(i, 1)
i = -1
}
} else {
for(let i = 0; i < arr2.length; i++) {
if(arr1.indexOf(arr2[i]) !== -1) {
let arr1_index = arr1.indexOf(arr2[i])
let arr2_index = i
empty.push(arr2[i])
// 剔除重复元素得到新元素
arr1.splice(arr1_index, 1)
}
arr2.splice(i, 1)
i = -1
}
}
return empty
}

这里需要解释一下为什么无论匹配与否都要执行 i = -1，和剔除短数组内的元素

第一个原因是如果有匹配项出现，并且剔除，那么短数组的长度就会变短，但i值依旧会增加，导致短数组无法遍历完成，所以每次让它在i++前恢复为-1，这样每次都会从0开始，即从头开始遍历

第二个原因是为了减少不必要的遍历次数，比如有两个数组[3,2,1,3,2,1] 和 [1,1,1,1,1,1,1,1,1,1,1]，如果仅仅把i=-1放在匹配条件下并剔除重复元素，那么在下一次遍历时又会从头开始遍历，以这个例子来看，[3,2]如果不剔除，每次都会遍历，这是多余的，故而要剔除。

注：如果有bug请告知于我，不吝赐教！与君共勉！