【Web前端问题】求两个数组的并集减去交集的部分，有什么好的算法？
var arr1 = [1,2,3,4,5,6,7]var arr2 = [3,5,7,9,12,14]
求两个数组的去除重复元素后(指将两边的重复元素都删除，例如3重复，则在结果中不能有3，与数组去重不同)的合并的数组，即数组的并集减交集的部分，不知道这个部分有什么数学名称没有。求一个时间复杂度较低的算法？
回答：
求两个集合不重合的部分，可以先求两个集合的并集，然后去掉公共的元素。
A∪B - A∩B = { x | (x∈A & x∉B) || (x∉A & x∈B) }
用程序的思路来实现是：
对两个数组合并，然后使用filter方法过滤掉数组a和b中的交集元素。将a.concat(b)中在a不在b中和在b不在a中的元素过滤出来。主要会涉及到数组中是否含有某个元素的判断，有Array.prototype.indexOf，Set的has方法，Array.prototype.includes三种实现方式。
利用ES5的indexOf方法在不考虑NaN情况下的实现方法：
function difference(a,b) { return a.concat(b).filter(function(v) {
return a.indexOf(v) === -1 || b.indexOf(v) === -1
})
}
利用ES6新增的Set集合方法，结合filter方法对合并的数组进行过滤。
function difference(a, b) { let aSet = new Set(a)
let bSet = new Set(b)
return a.concat(b).filter(v => !aSet.has(v) || !bSet.has(v))
}
利用ES7新增的Array.prototype.includes数组方法，用于返回一个数组是否包含指定元素，结合filter方法对合并的数组进行过滤。
function difference(a, b) { return a.concat(b).filter(v => !a.includes(v) || !b.includes(v))
}
回答：
用 set 做索引再遍历较短的 O(n)
var s1 = new Set(arr1)var s2 = new Set(arr2)
if (s1.size > s2.size) { [s1, s2] = [s2, s1] } // 让 s1 较短
s1.forEach(n => s2.has(n) && (s1.delete(n), s2.delete(n)))
var result = [...s1, ...s2]
回答：
這個結果叫symmetric difference, 在set或multiset上都有定義
複雜度..一般就O(n)了
回答：
var arr1 = [1,2,3,4,5,6,7];var arr2 = [3,5,7,9,12,14];
const s = new Set();
let arr = arr1.concat(arr2);
arr.forEach(x => s.add(x));
console.log(s);
----------看错问题了，答案有误，上面的只是去重了，看下面-------------
----------基础的for循环遍历一下就能搞定---------------
var arr1 = [1,2,3,4,5,6,7];var arr2 = [3,5,7,9,12,14];
var arr = [];
for(let i=0; i < arr1.length; i++){
if (!arr2.includes(arr1[i])) {
arr.push(arr1[i]);
}
}
for(let i=0; i < arr2.length; i++){
if (!arr1.includes(arr2[i])) {
arr.push(arr2[i]);
}
}
console.log(arr);
回答：
第一种方法，for
for(let i=0,len=arr2.length;i++){ if(arr1.indexOf(arr2[i])===-1){
arr1.push(arr2[i]);
}
}
第二种，concat和filter，原理就是合并再去重
var arr=arr1.concat(arr2);arr=arr.filter(function(item,index,self){
return self.indexOf(item) == index;
});
回答：
本人想起一种算法，利用哈希表，时间复杂度应该是O(n)，但是耗费一定的空间，不知是否有更好的解法，代码如下：
function getResult(arr1,arr2){ var obj = {};
arr1.forEach(function(item){
obj[item] = true;
})
arr2.forEach(function(item){
if(obj[item]){
obj[item] = false;
}
else{
obj[item] = true;
}
})
var res = [];
for(var p in obj){
if(obj[p]){
res.push(parseInt(p))
}
}
return res;
// return Object.keys(obj).filter(function(item){
// return obj[item] == true;
// })
}
回答：
方法一，查询表
var arr1 = [1, 2, 3, 4, 5, 6, 7];var arr2 = [3, 5, 7, 9, 12, 14];
// 生成表1
var set1 = arr1.reduce((all, n) => {
return all.add(n);
}, new Set());
// 生成表2
var set2 = arr2.reduce((all, n) => {
return all.add(n);
}, new Set());
// 找到列表1中不存在于列表2的
var result1 = arr1.filter(n => !set2.has(n));
// 找到列表2中不存在于列表1的
var result2 = arr2.filter(n => !set1.has(n));
// 组合起来
var result = [...result1, ...result2];
方法二，统计计重
// 合并两个列表const all = [...arr1, ...arr2]
.reduce((all, n) => {
// 对每个值计数
all.set(n, (all.get(n) || 0) + 1);
return all;
}, new Map());
// 选取计数为 1 的
result = Array.from(all.keys())
.filter(n => all.get(n) === 1);
结果都是：
[ 1, 2, 4, 6, 9, 12, 14 ]
补充一下
如果不用 ES6，可以使用第一种方法，去掉生成 set 的过程，把 set.has() 改成按数组遍历查找。
回答：
比较朴实的算法...，思路就是先对两个数组去重——>求交集——>求并集——>并集减交集，代码如下：
function newarr(arr,brr) { //去掉两个数组中各自重复的部分
function unique (crr) {
let brr =[];
for (let i=0; i<crr.length; i++) {
if (brr.indexOf(crr[i]) < 0) {
brr.push(crr[i]);
}
}
return brr;
}
//去重后的两个新数组
let purearr = unique(arr),
purebrr = unique(brr);
let sum=[],
intersection=[];
//求两个已去重数组的交集
function same(arr,brr) {
let samearr = [];
for (let i=0; i<arr.length; i++) {
let temp = arr[i];
for (let j=0; j<brr.length; j++) {
if (brr[j] === temp) {
samearr.push(brr[j]);
}
}
}
return samearr;
}
intersection=same(purearr,purebrr);
//求两个已经各自去重的数组的并集
function add (arr,brr) {
for (let i=0; i < arr.length; i++) {
let temp = arr[i];
for (let j=0; j<purebrr.length; j++) {
if (purebrr[j] === temp) {
purebrr.splice(j,1);
}
}
}
return arr.concat(brr);
}
sum = add(purearr,purebrr)
//对并集的数组去掉交集的元素
for (let i=0; i<intersection.length; i++) {
let temp=intersection[i];
for (let j=0; j<sum.length; j++) {
if (sum[j] === temp) {
sum.splice(j,1);
}
}
}
return sum;
}
回答：
先做concat，剩下的就是重算法的事情了，最简单的可以想到利用对象属性集合中元素的互异性。
回答：
/** * @brieaf 数组合并去重
* @param array1
* @param array2
* @return array
*/
function mergeResetArray(array1, array2) {
if ( ( array1 == null ) || ( array1 == undefined) || ( array2 == null ) || ( array2 == undefined) ) {
return false;
}
var array = [];
if (array1.constructor !== Array ) {
array[0] = array1;
} else {
array1.forEach(function (val, index) {
//将array1去重压入压入新数组
if ( array.indexOf(val) === -1 ) {
array.push(val);
}
});
}
if (array2.constructor !== Array) {
array.push(array2);
} else {
//循环array2，判断当前value是否在新数组last中，不在则压入last数组
array2.forEach(function (v, i) {
if ( array.indexOf(v) === -1 ){
array.push(v);
}
})
}
return array;
}
// var array1 = [1,2,2,5,7];
var array1 = 3;
var array2 = [3,4,5,5,6,7,8];
console.log(mergeResetArray(array1,array2));
回答：
python 的话直接使用异或即可--> ^
{1, 2} ^ {2, 4}
不过要先分别去重
回答：
利用对象的性质实现
var arr2key = (arr, o = {}) => { return arr.reduce((acc, cur) => {
acc[cur] = '√';
return acc;
}, o);
}
var mergeAsObj = A => B => {
return arr2key(B, arr2key(A));
}
var obj2arr = Object.keys;
// 组装
var arrMerge = A => B => {
return obj2arr(
mergeAsObj(A)(B)
)
}
ScreenShot
以上是 【Web前端问题】求两个数组的并集减去交集的部分，有什么好的算法？ 的全部内容， 来源链接： utcz.com/a/143721.html
