尝试使用 Javascript 解决对称差异

IT技术 javascript arrays symmetric-difference
2021-02-20 11:03:22

我正在尝试使用实现以下目标的 javascript 找出对称差异的解决方案：

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

因此，例如，如果输入是 ([1, 1, 2, 6], [2, 3, 5], [2, 3, 4])，则解将是 [1, 1, 6, 5 , 4]。

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

创建一个函数，该函数接受两个或多个数组并返回所提供数组的对称差的数组。

数学术语对称差是指两个集合中的元素属于第一组或第二组，但不属于两者。

尽管我下面的解决方案找到了每个数组唯一的数字，但它消除了出现多次的所有数字并且不保持数字的顺序。

我的问题与在 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 < 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]
6个回答

与所有问题一样，最好从编写算法开始：

连接数组的版本，其中每个数组都被过滤以包含除了当前数组之外没有其他数组包含的那些元素

然后用JS写下来：

function sym() {
  var arrays = [].slice.apply(arguments);

  return [].concat.apply([],               // concatenate
    arrays.map(                            // versions of the arrays
      function(array, i) {                 // where each array
        return array.filter(               // is filtered to contain
          function(elt) {                  // those elements which
            return !arrays.some(           // no array
              function(a, j) {             // 
                return i !== j             // other than the current one
                  && a.indexOf(elt) >= 0   // contains
                ;
              }
            );
          }
        );
      }
    )
  );
}

无注释版本，使用 ES6 编写更简洁：

function sym(...arrays) {
  return [].concat(arrays . 
    map((array, i) => array . 
      filter(elt => !arrays . 
        some((a, j) => i !== j && a.indexOf(elt) >= 0))));
}
谢谢你。您的解决方案也非常有帮助，向我展示了如何使用 Javascript 方法处理数组。
2021-04-24 11:03:22

这是一个使用Set对象来加快查找速度的版本。这是基本逻辑：

  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]。

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

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 对象。这会跳过由该数组构成的 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 < 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);
}

@davisec52 - 该Set对象是新浏览器支持的新功能。它是 ES6 Javascript 规范的一部分。这就是为什么我提供了在不支持该Set对象的浏览器中工作的第二个代码示例。
2021-04-21 11:03:22
@davisec52 - 我刚刚注意到你在问题中链接的另一个解决方案也是我的。我想我只是喜欢这类问题。
2021-05-09 11:03:22
我添加了一个适用于 IE 的代码版本（回到 IE9）。在IE的无限智慧中（即使是IE11），虽然支持Set对象，但不支持将数组传递给构造函数。因此，上面代码的第二个版本测试是否缺少Set对象或 IE 功能不佳的对象，并使用了一个非常小的 polyfill 替换来满足此功能的需求。
2021-05-09 11:03:22
谢谢！这让我难住了。在我的一生中，我无法弄清楚如何对您的解决方案如此清晰地显示的元素进行迭代和比较。非常感谢！
2021-05-14 11:03:22
你的回答很有启发性。将这些答案与您在问题上方提供的链接中给出的答案进行比较也很有启发性。我仍然是一个新手，我不知道 Set 对象，也不知道 has 的使用（如 set[setsIndex].has[item]）。
2021-05-20 11:03:22

我在研究 FCC 上的相同编码挑战时遇到了这个问题。我能够使用for和while循环解决它，但使用推荐的Array.reduce(). 在学习了大量关于.reduce数组和其他数组方法之后，我想我也会分享我的解决方案。

这是我解决它的第一种方法，不使用.reduce.

function sym() {
  var arrays = [].slice.call(arguments);

  function diff(arr1, arr2) {
    var arr = [];

    arr1.forEach(function(v) {
      if ( !~arr2.indexOf(v) && !~arr.indexOf(v) ) {
        arr.push( v );
      }
    });

    arr2.forEach(function(v) {
      if ( !~arr1.indexOf(v) && !~arr.indexOf(v) ) {
        arr.push( v );
      }
    });
    return arr;
  }

  var result = diff(arrays.shift(), arrays.shift());

  while (arrays.length > 0) {
    result = diff(result, arrays.shift());
  }

  return result;
}

在学习并尝试了各种方法组合后，我想出了这个我认为非常简洁易读的方法。

function sym() {
  var arrays = [].slice.call(arguments);

  function diff(arr1, arr2) {
    return arr1.filter(function (v) {
      return !~arr2.indexOf(v);
    });
  }

  return arrays.reduce(function (accArr, curArr) { 
    return [].concat( diff(accArr, curArr), diff(curArr, accArr) )
    .filter(function (v, i, self) { return self.indexOf(v) === i; });
  });

}

最后.filter一行我认为对数组进行重复数据删除非常酷。我在这里找到了它，但由于方法链的原因，将其修改为使用第三个回调参数而不是命名数组。

这个挑战非常有趣！

// Set difference, a.k.a. relative compliment
const diff = (a, b) => a.filter(v => !b.includes(v))

const symDiff = (first, ...rest) => 
  rest.reduce(
    (acc, x) => [
      ...diff(acc, x), 
      ...diff(x, acc),
    ], 
    first,
  )    

/* - - - */
console.log(symDiff([1, 3], ['Saluton', 3]))    // [1, 'Saluton']
console.log(symDiff([1, 3], [2, 3], [2, 8, 5])) // [1, 8, 5]

只需使用_.xor或复制 lodash 代码。

其它你可能感兴趣的问题
上一篇计算数组中字符串的实例 下一篇在 android 浏览器中播放 html5 音频