20

我正在尝试使用实现以下目标的 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]
4

19 回答 19

27

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

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

然后在 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))));
}
于 2015-06-15T12:41:17.140 回答
13

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

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

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

于 2015-06-14T22:15:52.600 回答
9

我在研究 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一行我认为对数组进行重复数据删除非常酷。我在这里找到了它，但由于方法链接，将其修改为使用第三个回调参数而不是命名数组。

这个挑战很有趣！

于 2016-03-04T21:33:48.273 回答
6 

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

于 2019-01-09T06:30:21.343 回答
4

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

于 2015-10-30T07:05:11.740 回答
4

另一个简单但可读的解决方案： 

 
/*
This filters arr1 and arr2 from elements which are in both arrays
and returns concatenated results from filtering.
*/
function symDiffArray(arr1, arr2) {
  return arr1.filter(elem => !arr2.includes(elem))
             .concat(arr2.filter(elem => !arr1.includes(elem)));
}

/*
Add and use this if you want to filter more than two arrays at a time.
*/
function symDiffArrays(...arrays) {
  return arrays.reduce(symDiffArray, []);
}

console.log(symDiffArray([1, 3], ['Saluton', 3])); // [1, 'Saluton']
console.log(symDiffArrays([1, 3], [2, 3], [2, 8, 5])); // [1, 8, 5]

使用的函数： Array.prototype.filter() | Array.prototype.reduce() | Array.prototype.includes()

于 2018-05-05T20:17:09.613 回答
4 
function sym(arr1, arr2, ...rest) {

  //creating a array which has unique numbers from both the arrays
  const union = [...new Set([...arr1,...arr2])];

  // finding the Symmetric Difference between those two arrays
  const diff = union.filter((num)=> !(arr1.includes(num) && arr2.includes(num)))

  //if there are more than 2 arrays
  if(rest.length){
    // recurrsively call till rest become 0 
    // i.e.  diff of 1,2 will be the first parameter so every recurrsive call will reduce     //  the arrays till diff between all of them are calculated.

    return sym(diff, rest[0], ...rest.slice(1))
  }
  return diff
}
于 2018-07-27T11:09:32.157 回答
3

创建一个包含所有唯一值计数的 Map（跨数组）。然后连接所有数组，并使用 Map 过滤非唯一值。

const symsym = (...args) => {
  // create a Map from the unique value of each array
  const m = args.reduce((r, a) => {
    // get unique values of array, and add to Map
    new Set(a).forEach((n) => r.set(n, (r.get(n) || 0) + 1));
    
    return r;
  }, new Map());
  
  // combine all arrays
  return [].concat(...args)
    // remove all items that appear more than once in the map
    .filter((n) => m.get(n) === 1); 
};

console.log(symsym([1, 1, 2, 6], [2, 3, 5], [2, 3, 4])); // => Desired answer: [1, 1, 6, 5, 4]

于 2018-03-23T10:37:28.393 回答
2

这是使用高阶函数的 JS 代码

    function sym(args) {
      var output;
      output = [].slice.apply(arguments).reduce(function(previous, current) {
        current.filter(function(value, index, self) { //for unique
          return self.indexOf(value) === index;
        }).map(function(element) { //pushing array
          var loc = previous.indexOf(element);
          a = [loc !== -1 ? previous.splice(loc, 1) : previous.push(element)];
        });
        return previous;
      }, []);
      document.write(output);
      return output;
    }

    sym([1, 2, 3], [5, 2, 1, 4]);

它会将输出返回为：[3,5,4]

于 2015-07-16T20:17:06.757 回答
2

纯 JavaScript 解决方案。

function diff(arr1, arr2) {
var arr3= [];
  for(var i = 0; i < arr1.length; i++ ){
    var unique = true;
     for(var j=0; j < arr2.length; j++){
          if(arr1[i] == arr2[j]){
               unique = false;
               break;
          }
     }
  if(unique){
    arr3.push(arr1[i]);}
  }
 return arr3;
}

function symDiff(arr1, arr2){
  return diff(arr1,arr2).concat(diff(arr2,arr1));
}

symDiff([1, "calf", 3, "piglet"], [7, "filly"])
//[1, "calf", 3, "piglet", 7, "filly"]
于 2015-10-30T07:05:56.273 回答
2

我的简短解决方案。最后，我通过 filter() 删除了重复项。

function sym() {
  var args = Array.prototype.slice.call(arguments);
  var almost = args.reduce(function(a,b){
    return b.filter(function(i) {return a.indexOf(i) < 0;})
    .concat(a.filter(function(i){return b.indexOf(i)<0;}));
  });
  return almost.filter(function(el, pos){return almost.indexOf(el) == pos;});
}

sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5]);

//Result: [4,5,1]
于 2016-03-04T13:55:57.947 回答
2 

function sym(args) {
  var initialArray = Array.prototype.slice.call(arguments);
  var combinedTotalArray = initialArray.reduce(symDiff);

  
  // Iterate each element in array,  find values not present in other array and push values in combinedDualArray if value is not there already
  // Repeat for the other array (change roles)
  function symDiff(arrayOne, arrayTwo){
    var combinedDualArray = [];
    arrayOne.forEach(function(el, i){
      if(!arrayTwo.includes(el) && !combinedDualArray.includes(el)){
        combinedDualArray.push(el);
      }
    });
      
    arrayTwo.forEach(function(el, i){
      if(!arrayOne.includes(el) && !combinedDualArray.includes(el)){
        combinedDualArray.push(el);
      }
    });
    combinedDualArray.sort();
    return combinedDualArray;
  }
  
  return combinedTotalArray;
}

console.log(sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5]));

于 2018-02-23T04:52:39.390 回答
1

这对我有用：

function sym() {
  var args = [].slice.call(arguments);
  
  var getSym = function(arr1, arr2) {
    return arr1.filter(function(each, idx) {
      return arr2.indexOf(each) === -1 && arr1.indexOf(each, idx + 1) === -1;
    }).concat(arr2.filter(function(each, idx) {
      return arr1.indexOf(each) === -1 && arr2.indexOf(each, idx + 1) === -1;
    }));
  };
  
  var result = getSym(args[0], args[1]);
  var len = args.length - 1, i = 2;
  while (--len) {
    result = [].concat(getSym(result, args[i]));
    i++;
  }
  
  return result;
}

console.info(sym([1, 1, 2, 5], [2, 2, 3, 5], [6, 8], [7, 8], [9]));

于 2016-10-12T22:53:48.663 回答
1

替代方案：使用地图内的查找而不是数组

function sym(...vs){
    var has = {};
    //flatten values
    vs.reduce((a,b)=>a.concat(b)).
        //if element does not exist add it (value==1)
        //or mark it as multiply found value > 1
        forEach(value=>{has[value] = (has[value]||0)+1});
    return Object.keys(has).filter(x=>has[x]==1).map(x=>parseInt(x,10));
}
console.log(sym([1, 2, 3], [5, 2, 1, 4],[5,7], [5]));//[3,4,7])
于 2016-11-17T08:41:38.787 回答
1

嘿，如果有人感兴趣，这是我的解决方案：

function sym (...args) {
  let fileteredArgs = [];
  let symDiff = [];
  args.map(arrayEl =>
    fileteredArgs.push(arrayEl.filter((el, key) =>
      arrayEl.indexOf(el) === key
      )
    )
  );

  fileteredArgs.map(elArr => {
    elArr.map(el => {
      let index = symDiff.indexOf(el);
      if (index === -1) {
        symDiff.push(el);
      } else {
        symDiff.splice(index, 1);
      }
    });
  });

  return (symDiff);
}

console.log(sym([1, 2, 3, 3], [5, 2, 1, 4]));

于 2018-07-06T12:31:47.377 回答
1

此函数删除重复项，因为对称差异的原始概念适用于集合。在这个例子中，函数以这种方式对集合进行操作： ((A △ B) △ C) △ D ...

function sym(...args) {
    return args.reduce((old, cur) => {
        let oldSet = [...new Set(old)]
        let curSet = [...new Set(cur)]
        return [
            ...oldSet.filter(i => !curSet.includes(i)),
            ...curSet.filter(i => !oldSet.includes(i))
        ]
    })
}

// Running> sym([1, 1, 2, 6], [2, 3, 5], [2, 3, 4])
console.log(sym([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]))
// Return>  [1, 6, 5, 2, 4]

于 2020-11-02T04:26:37.243 回答
1

这是解决方案

let a=[1, 1, 2, 6]
let b=[2, 3, 5];
let c= [2, 3, 4]

let result=[...a,...b].filter(item=>!(a.includes(item) && b.includes(item) ))
result=[...result,...c].filter(item=>!(b.includes(item) && c.includes(item) ))

console.log(result)  //[1, 1, 6, 5, 4]
于 2021-01-21T16:56:42.373 回答
0

简洁的解决方案使用

const symPair = (a, b) => 
  [...a.filter(item => !b.includes(item)),
  ...b.filter(item => !a.includes(item))]

const sym = (...args) => [...new Set(args.reduce(symPair))]

该函数symPair适用于两个输入数组，该函数sym适用于两个或更多数组，symPair用作减速器。

const symPair = (a, b) => 
  [...a.filter(item => !b.includes(item)),
  ...b.filter(item => !a.includes(item))]

const sym = (...args) => [...new Set(args.reduce(symPair))]

console.log(sym([1, 2, 3], [2, 3, 4], [6]))

于 2021-09-02T09:40:40.293 回答
0 

const removeDuplicates = (data) => Array.from(new Set(data));
const getSymmetric = (data) => (val) => data.indexOf(val) === data.lastIndexOf(val)

function sym(...args) {
  let joined = [];
  args.forEach((arr) => {
    joined = joined.concat(removeDuplicates(arr));
    joined = joined.filter(getSymmetric(joined))
  });
 return joined;
}


console.log(sym([1, 2, 3], [5, 2, 1, 4]));

于 2021-11-21T19:21:08.347 回答