比较 2 个数组的差异（找到对称差异）

Question

这应该是一个简单的算法，但我无法理解其中的逻辑。我需要使用 2 个数组并仅保留在一个数组或另一个数组中找到的值，而不是同时保留两个数组中的值。

例如，如果我有

arr1 [1,2,3,6]

arr2 [2,3,4,5,7]

我想再次拥有 2 个数组

arr1 [1,6]
arr2 [4,5,7]

编辑：

我删除了我的旧代码并放入了一些其他的工作代码。仍然不是很漂亮，但至少可以工作。我需要做的就是将 arr3 存储到 arr1 并将 arr4 存储到 arr2。

    var arr3 = [];
    var arr4 = [];

    var foundMatch = false;

    //find all arr1 elements that don't match arr2 elements
    //store into arr4
    for(var i=0; i<arr1.length; i++)
    {
        foundMatch = false;
        for(var j=0; j<arr2.length; j++)
        {
            if(arr1[i] == arr2[j])
            {
                console.log("match found for [%s] [%s]", i, j);
                foundMatch = true;
                break;
            }
        }
        if(!foundMatch)
        {
            arr4.push(arr1[i]);
        }
    }

    //find all arr2 elements not in arr1
    //store in arr3
    for(var i=0; i<arr2.length; i++)
    {
        foundMatch = false;
        for(var j=0; j<arr1.length; j++)
        {
            if(arr2[i] == arr1[j])
            {
                console.log("match found for [%s] [%s]", i, j);
                foundMatch = true;
                break;
            }
        }
        if(!foundMatch)
        {
            arr3.push(arr2[i]);
        }
    }

Answer 1

您正在尝试为您的 2 组 A 和 B 获取 A - B 和 B - A

arr1 = [1,2,3,6]
arr2 = [2,3,4,5,7]

var required1 = arr1.filter((x) => arr2.indexOf(x) < 0)
var required2 = arr2.filter((x) => arr1.indexOf(x) < 0)

console.log(required1, required2);

Answer 2

就时间复杂度而言，最快的解决方案是从一个数组创建 Set 或 hash -> O(N)，然后遍历另一个数组以比较元素是否不是集合 -> O(M) -> 然后将它添加到 diffs 数组中。这里的主要好处是设置查找时间是恒定的。此解决方案还具有 space 的复杂性 O(N) 用于构建集合。

您也可以对另一个数组重复此操作，总计 O(N) + O(M) + O(N) + O(M)，当移除常数因子时，时间复杂度仅为 O(N+M)。

为第二个数组构建集合给出的总 space 复杂度为 O(N+M)。

// Total complexity
// Time:  O(N+M)
// Space: O(N+M)

// time complexities for each step shown bellow

let N = [1,2,3,6]
let M = [2,3,4,5,7]

const setForN = new Set(N); // O(N)
const setForM = new Set(M); // O(M)

// O(N + M) at this point

const answerN = N.filter(n => !setForM.has(n)) // O(N)
const answerM = M.filter(m => !setForN.has(m)) // O(M)

// O(N + M) + O(N + M) at this point, which is just O(N + M)

console.log(answerN, answerM);

ES5 解决方案：

var N = [1,2,3,6]
var M = [2,3,4,5,7]

var setOfNumbers = function(arr) {
  return arr.reduce(function(set, item) {
    return Object.defineProperty(set, item, { value: item });
  }, Object.create(null));
}
var setForN = setOfNumbers(N);
var setForM = setOfNumbers(M);

var answerN = N.filter(function(n) { return typeof setForM[n] !== 'number' });
var answerM = M.filter(function(m) { return typeof setForN[m] !== 'number' });

console.log(answerN, answerM);

另一种方法是按照其他答案的建议去做，对于 N -> O(N) 中的每个元素，检查它是否存在于 M -> O(M)，并将其添加到 diffs 数组中。对另一个数组重复此操作。

这有更好的、恒定的、space 复杂度 O(1) 但二次方 O(N*M) 时间较慢。

// Total Complexity:
// Time:  O(N*M)
// Space: O(1)

let N = [1,2,3,6]
let M = [2,3,4,5,7]

// For every element in N -> O(N)
// Iterate through M and check if it's there -> O(M)
// Total: O(N*M)
const answerN = N.filter(n => !M.includes(n));

// For every element in M -> O(M)
// Iterate through N and check if it's there -> O(N)
// Total: O(M*N)
const answerM = M.filter(m => !N.includes(m));

// O(N*M) + O(M*N) at this point, which is just O(N*M)

console.log(answerN, answerM);

Answer 3

您可以使用数组过滤器方法来检查 2 个数组的交集：考虑以下创建 2 个仅包含唯一值的新数组的代码：

let arr1 = [1,2,3,6];
let arr2 =  [2,3,4,5,7];

let newArr1 = arr1.filter((itm)=>{
    return arr2.indexOf(itm) == -1
});

let newArr2 = arr2.filter((itm)=>{
    return arr1.indexOf(itm) == -1
});

选择退出 newArr1 和 newArr2 是：

[1, 6] 
[4, 5, 7]

Answer 4

var arr1 = [1,2,3,6],

    arr1Copy = arr1,

    arr2 = [2,3,4,5,7];

arr1 = arr1.filter(function(outerItem){
  return !arr2.some(function(innerItem){
    return outerItem === innerItem;
  })
})

arr2 = arr2.filter(function(outerItem){
  return !arr1Copy.some(function(innerItem){
    return outerItem === innerItem;
  })
})

比较 2 个数组的差异（找到对称差异）

Comparing 2 arrays for differences (find symmetric difference)

javascript

arrays

algorithm

symmetric-difference