尝试使用 Javascript 解决对称差异 [英] Trying to solve symmetric difference using Javascript

问题描述

我正在尝试找出对称的解决方案使用 javascript 完成以下操作的区别目标:

I am trying to figure out a solution for symmetric difference using javascript that accomplishes the following objectives:

• 接受未指定数量的数组作为参数
• 保留数组中数字的原始顺序
• 不会删除单个数组中的重复数字
• 删除数组中出现的重复项

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

Thus, for example, if the input is ([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]), the solution would be, [1, 1, 6, 5, 4].

我正在尝试解决这个问题，因为它是在线提出的挑战编码社区.挑战的确切说明状态，

I am trying to solve this as challenge given by an online coding community. The exact instructions of the challenge state,

创建一个接受两个或多个数组并返回一个数组的函数提供的数组的对称差异.

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.

虽然我在下面的解决方案找到的数字是每个数组都是唯一的，它消除了所有出现的数字不止一次并且不保持数字的顺序.

Although my solution below finds the numbers that are unique to each array, it eliminates all numbers occuring more than once and does not keep the order of the numbers.

我的问题与在 在javascript中的多个数组中查找对称差异/唯一元素.然而，解决方案不保留数字的原始顺序，也不保留单个数组中出现的唯一数字的重复项.

My question is very close to the one asked at finding symmetric difference/unique elements in multiple arrays in javascript. However, the solution does not preserve the original order of the numbers and does not preserve duplicates of unique numbers occurring in single arrays.

function sym(args){
    var arr = [];
    var result = [];
    var units;
    var index = {};
    for(var i in arguments){
        units = arguments[i];

    for(var j = 0; j < units.length; 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 对象来加快查找速度的版本.这是基本逻辑:

Here's a version that uses the Set object to make for faster lookup. Here's the basic logic:

1. 它将作为参数传递的每个数组放入一个单独的 Set 对象中(以促进快速查找).
2. 然后，它迭代传入数组的每个对象，并将其与其他 Set 对象(不是由被迭代的数组构成的对象)进行比较.
3. 如果该项目在任何其他 Sets 中均未找到，则将其添加到结果中.

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

So, it starts with the first array [1, 1, 2, 6]. Since 1 is not found in either of the other arrays, each of the first two 1 values are added to the result. Then 2 is found in the second set so it is not added to the result. Then 6 is not found in either of the other two sets so it is added to the result. The same process repeats for the second array [2, 3, 5] where 2 and 3 are found in other Sets, but 5 is not so 5 is added to the result. And, for the last array, only 4 is not found in the other Sets. So, the final result is [1,1,6,5,4].

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

The Set objects are used for convenience and performance. One could use .indexOf() to look them up in each array or one could make your own Set-like lookup with a plain object if you didn't want to rely on the Set object. There's also a partial polyfill for the Set object that would work here in 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 < sets.length; 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，因此它只查找存在于其他数组中的项目.这允许它保留只出现在一个数组中的重复项.

One key part of this code is how it compares a given item to the Sets from the other arrays. It just iterates through the list of Set objects, but it skips the Set object that has the same index in the array as the array being iterated. That skips the Set made from this array so it's only looking for items that exist in other arrays. That allows it to retain duplicates that occur in only one array.

这是一个使用 Set 对象(如果存在)的版本，但如果不存在则插入一个很小的替换(因此这将在更旧的浏览器中工作):

Here's a version that uses the Set object if it's present, but inserts a teeny replacement if not (so this will work in more older browsers):

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 < sets.length; 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);
}

这篇关于尝试使用 Javascript 解决对称差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！