5

这应该是一个简单的算法，但我无法理解逻辑。我需要获取 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]);
        }
    }
4

4 回答 4

4

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

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

为第二个数组构建集合给出的总空间复杂度为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 数组中。对另一个数组重复。

这具有更好、恒定的空间复杂度，但二次时间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);

于 2017-04-24T19:26:50.307 回答
2

你正试图为你的2 套A - B和B - AAB 

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

于 2017-04-24T19:24:05.560 回答
0

您可以使用数组过滤方法来检查 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]
于 2017-04-24T19:26:55.527 回答
0 
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;
  })
})
于 2017-04-24T19:34:35.960 回答