探索利用JavaScript实现集合的对称差集算法

我试图找出对称的解决方案
差异使用Javascript完成以下
目标：

>接受一个未指定数量的数组作为参数
>保留数组中数字的原始顺序
>不会删除单个数组中的重复数字
>删除跨阵列发生的重复项

因此,例如,
如果输入是([1,1,2,6],[2,3,5],[2,3,4]),
解决方案是,[1,1,6,5,4].

我试图解决这个问题,因为网上提出了挑战
编码社区.挑战的确切说明
州,

Create a function that takes two or more arrays and returns an array

of the symmetric difference of the provided arrays.

The mathematical term symmetric difference refers to the elements in

two sets that are in either the first or second set, but not in both.

虽然我的解决方案下面找到了数字
每个阵列都是唯一的,它可以消除所有出现的数字
不止一次,不保持数字的顺序.

我的问题与finding symmetric difference/unique elements in multiple arrays in Javascript问的问题非常接近.但是,解决方案
不保留数字的原始顺序,也不保留单个数组中出现的唯一数字的重复.

function sym(args){
var arr = [];
var result = [];
var units;
var index = {};
for(var i in arguments){
units = arguments[i];
for(var j = 0; j arr.push(units[j]);
}
}
arr.forEach(function(a){
if(!index[a]){
index[a] = 0;
}
index[a]++;
});
for(var l in index){
if(index[l] === 1){
result.push(+l);
}
}
return result;
}
symsym([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]); // => Desired answer: [1, 1, 6. 5. 4]


解决方法:

这是一个使用Set对象进行更快查找的版本.这是基本逻辑：

>它将每个数组作为参数传递给一个单独的Set对象(以便于快速查找).
>然后,它迭代每个传入的数组并将其与其他Set对象(不是从正在迭代的数组中生成的对象)进行比较.
>如果在任何其他集中找不到该项,则将其添加到结果中.

所以,它从第一个数组[1,1,2,6]开始.由于在其他任何一个数组中都找不到1,因此前两个1值中的每一个都会添加到结果中.然后在第二组中找到2,因此不将其添加到结果中.然后在其他两个集合中找不到6,因此将其添加到结果中.对于第二个阵列[2,3,5]重复相同的过程,其中2和3在其他集合中找到,但是5不是5,因此将5添加到结果中.并且,对于最后一个数组,在其他集合中找不到4个.所以,最终的结果是[1,1,6,5,4].

Set对象用于方便和性能.可以使用.indexOf()在每个数组中查找它们,或者如果您不想依赖Set对象,则可以使用普通对象进行自己的类似Set的查找.还有一个Set对象的部分polyfill,可以在this answer中使用.

function symDiff() {
var sets = [], result = [];
// make copy of arguments into an array
var args = Array.prototype.slice.call(arguments, 0);
// put each array into a set for easy lookup
args.forEach(function(arr) {
sets.push(new Set(arr));
});
// now see which elements in each array are unique
// e.g. not contained in the other sets
args.forEach(function(array, arrayIndex) {
// iterate each item in the array
array.forEach(function(item) {
var found = false;
// iterate each set (use a plain for loop so it's easier to break)
for (var setIndex = 0; setIndex // skip the set from our own array
if (setIndex !== arrayIndex) {
if (sets[setIndex].has(item)) {
// if the set has this item
found = true;
break;
}
}
}
if (!found) {
result.push(item);
}
});
});
return result;
}
var r = symDiff([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]);
log(r);
function log(x) {
var d = document.createElement("div");
d.textCOntent= JSON.stringify(x);
document.body.appendChild(d);
}

此代码的一个关键部分是它如何将给定项与其他数组中的集进行比较.它只是遍历Set对象列表,但它跳过了与正在迭代的数组在数组中具有相同索引的Set对象.这会跳过从此数组生成的Set,因此它只查找其他数组中存在的项.这允许它保留仅在一个数组中出现的重复项.

这是一个使用Set对象的版本,如果它存在,但是如果没有则插入一个小的替换(所以这将适用于更旧的浏览器)：

function symDiff() {
var sets = [], result = [], LocalSet;
if (typeof Set === "function") {
try {
// test to see if constructor supports iterable arg
var temp = new Set([1,2,3]);
if (temp.size === 3) {
LocalSet = Set;
}
} catch(e) {}
}
if (!LocalSet) {
// use teeny polyfill for Set
LocalSet = function(arr) {
this.has = function(item) {
return arr.indexOf(item) !== -1;
}
}
}
// make copy of arguments into an array
var args = Array.prototype.slice.call(arguments, 0);
// put each array into a set for easy lookup
args.forEach(function(arr) {
sets.push(new LocalSet(arr));
});
// now see which elements in each array are unique
// e.g. not contained in the other sets
args.forEach(function(array, arrayIndex) {
// iterate each item in the array
array.forEach(function(item) {
var found = false;
// iterate each set (use a plain for loop so it's easier to break)
for (var setIndex = 0; setIndex // skip the set from our own array
if (setIndex !== arrayIndex) {
if (sets[setIndex].has(item)) {
// if the set has this item
found = true;
break;
}
}
}
if (!found) {
result.push(item);
}
});
});
return result;
}
var r = symDiff([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]);
log(r);
function log(x) {
var d = document.createElement("div");
d.textCOntent= JSON.stringify(x);
document.body.appendChild(d);
}