尝试使用Javascript解决对称差异

Question

我试图找到一个使用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]

Answer 1

与所有问题一样,最好开始编写算法:

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

然后在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))));
}

Answer 2

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

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

所以,它从第一个数组开始[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对象的版本,如果它存在,但如果没有,则插入一个小的替换(所以这将适用于更旧的浏览器):

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);
}

Answer 3

我在对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一行我认为重复数组是非常酷的.我在这里找到它,但由于方法链接,修改它以使用第3个回调参数而不是命名数组.

这个挑战很有趣!

Answer 4

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