两个数组：查找第一个数组中缺少的项目，查找第二个数组中缺少的项目

Question

假设有两个数组：

const array1 = [1,2,3];
const array2 = [2,3,4];

现在，我想获取这两个数组的所有差异并将它们放入两个新数组中。一个数组将用于第一个缺失的所有项目。另一个将用于第二个中丢失的项目。结果看起来像这样：

const newArray1 = [1];
const newArray2 = [4];

我该怎么做？最有效的方法是什么？

Answer 1

这样的事情会相对有效，你只需要遍历两个数组。

遍历第一个数组并将任何缺失的项目添加到第一个 newArray。对第二个数组重复相同的过程。

如果您只需要循环遍历数组一次，则需要执行类似于下面的操作，但只循环遍历最长的数组。

const array1 = [1,2,3];
const array2 = [2,3];

function diff (arr1, arr2) {
  const newA1 = [];
  const newA2 = [];
  arr1.forEach((item, i) => {
    let index = arr2.findIndex(it => it === item);
    if(index < 0) newA1.push(item);
  });
  arr2.forEach((item, i) => {
    let index = arr1.findIndex(it => it === item);
    if(index < 0) newA2.push(item);
  });
  return [newA1, newA2];
}

console.log(diff(array1, array2));

更有效的方法（仅循环遍历 1 个数组）。通过这种方式，您可以选择最长的数组，遍历它，并检查长数组的当前项的重复项，如果辅助数组中的项存在于同一位置，则还要检查最长数组中此项的重复项.这个方法和上面的方法类似，但是每次循环只有1个。

const array1 = [1,2,3];
const array2 = [3,4,5];

function diff (arr1, arr2) {
  const newA1 = [];
  const newA2 = [];
  let baseArr, secondaryArr;
  
  if(arr1.length > arr2.length) {
    baseArr = arr1;
    secondaryArr = arr2;
  } else {
    baseArr = arr2;
    secondaryArr = arr1;
  }
  
  baseArr.forEach((item, i) => {
    const secondaryArrI = secondaryArr.findIndex(it => it === item);
    if(secondaryArrI < 0) newA1.push(item)
    if(typeof secondaryArr[i] !== "undefined") {
      const removeI = baseArr.findIndex(it => it === secondaryArr[i]);
      
      if(removeI < 0) newA2.push(secondaryArr[i]);
    
    }
  })
  
  return [newA1, newA2];
}

console.log(diff(array1, array2));

Answer 2

const array1 = [2,1,3,5,2,1,3,5];
const array2 = [4,3,2,6,7,4,3,2,6,7];

function diff(arr1, arr2) {
    const dontAddDuplicates = true;
    arr1.sort();
    arr2.sort();
    let a1 = [];
    let a2 = [];
    let i = 0;
    let j = 0;
    while (i < array1.length || j < array2.length) {
        if (i >= arr1.length) {
         if (!dontAddDuplicates || (a2.length == 0 || a2[a2.length - 1] != arr2[j])) {
            a2.push(arr2[j]);
         }
         j++;
      } else if (j >= array2.length) {
         if (!dontAddDuplicates || (a1.length == 0 || a1[a1.length - 1] != arr1[i])) {
            a1.push(arr1[i]);
         }
         i++;
      }  else if (arr1[i] < arr2[j]) {
         if (!dontAddDuplicates || (a1.length == 0 || a1[a1.length - 1] != arr1[i])) {
            a1.push(arr1[i]);
         }
         i++;
      } else if (arr2[j] < arr1[i]) {
         if (!dontAddDuplicates || (a2.length == 0 || a2[a2.length - 1] != arr2[j])) {
            a2.push(arr2[j]);
         }
         j++;
      } else {
         // Same value, do nothing
         i++;
         j++;
      }
    }
    return [a1, a2];
}

console.log(diff(array1, array2));
// OUTPUT: [[1, 5], [4, 6, 7]]

这是使用排序的另一种可能的实现方式，但它具有以排序方式保留 array1 和 array2 的副作用。排序可以避免每次都重新扫描另一个数组。如果它们已经排序，那么很好，你可以跳过这一步。如果副作用是个问题，那么在调用排序之前使用 array1 和 array2 的深拷贝。

翻转dontAddDuplicates是否需要重复。我注意到其他实现没有考虑到这一点，但很容易添加。

运行时间应该是：SORT N + SORT M + N + M = SORT N = N LOG N 取决于你的输入大小和分布 SORT 将是重要的 O 符号 https://www.bigocheatsheet.com/

https://jsfiddle.net/buscgtL2/1/

如果您想在 N + M + N + M = N 时间内完成，您可以使用此实现，它使用哈希映射而不是排序。这对内存有不利影响 space.

const array1 = [2,1,3,5,2,1,3,5];
const array2 = [4,3,2,6,7,4,3,2,6,7];

function diff(arr1, arr2) {
    let dontAddDuplicates = true;
    let a1 = [];
    let a2 = [];
    let a1hash = {};
    let a2hash = {};
    for (let i = 0; i < arr1.length; i++) {
       a1hash[arr1[i]] = 0;
    }
    for (let i = 0; i < arr2.length; i++) {
       a2hash[arr2[i]] = 0;
    }
    for (let i = 0; i < arr1.length; i++) {
       if (!a2hash.hasOwnProperty(arr1[i])) {
          if (!dontAddDuplicates || a1hash[arr1[i]] == 0) {
             a1hash[arr1[i]] = 1;
             a1.push(arr1[i]);
          }
       }
    }
    for (let i = 0; i < arr2.length; i++) {
       if (!a1hash.hasOwnProperty(arr2[i])) {
          if (!dontAddDuplicates || a2hash[arr2[i]] == 0) {
             a2hash[arr2[i]] = 1;
             a2.push(arr2[i]);
          }
       }
    }
    return [a1, a2];
}

console.log(diff(array1, array2));
//OUTPUT: [[1, 5], [4, 6, 7]]

https://jsfiddle.net/2945y3an/1/

性能最差的算法是，对于每 N 个元素扫描数组 M 以搜索匹配项。这将是 N * M = N^2

Answer 3

Lodash difference 如果你不介意的话

const array1 = [1,2,3];
const array2 = [2,3,4];

console.log(_.difference(array1, array2));
console.log(_.difference(array2, array1));

.as-console-wrapper{min-height: 100%!important; top: 0}

<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.21/lodash.min.js"></script>

Answer 4

您可以使用 JavaScript.

的 Array.filter() along with Array.includes() 方法以非常简单的方式用最少的代码行实现它

工作演示：

const array1 = [1,2,3];
const array2 = [2,3,4];

const updatedArray1 = array1.filter(item => !array2.includes(item));
const updatedArray2 = array2.filter(item => !array1.includes(item));

console.log(updatedArray1); // [1]
console.log(updatedArray2); // [4]

两个数组：查找第一个数组中缺少的项目，查找第二个数组中缺少的项目

Two Arrays: Find items that are missing in the first, find items that are missing in the second

javascript

arrays

sorting