在Javascript中比较两个数组 - 返回差异

Question

假设我们有以下内容：

array1 = ['A', 'B', 'C', 'D', 'E']; array2 = ['C', 'E'];

有没有一种经过验证的快速解决方案来比较两个数组，返回一个不包含两个数组中都出现的值（这里是C和E）的数组。

array3 = ['A', 'B', 'D']

应该是解决方案的输出。(可能涉及jQuery) 感谢。

- Björn

---

这些数组总是有序的吗，和你示例中一样？如果是，那么只需遍历这些数组就可以在线性时间内完成。 - Ben Zotto

Answer 1

我接受了Matthews的解决方案，但不想忽略我刚发现的另一个更快的解决方案。

 var list1 = [1, 2, 3, 4, 5, 6];
 var list2 = ['a', 'b', 'c', 3, 'd', 'e'];
 var lookup = {};

 for (var j in list2) {
      lookup[list2[j]] = list2[j];
  }

  for (var i in list1) {
      if (typeof lookup[list1[i]] != 'undefined') {
          alert('found ' + list1[i] + ' in both lists');
          break;
 } 
 }

来源：优化循环以比较两个数组

- Björn

---

特别是当其中一个列表（这里是list2）需要与许多候选者（许多list1）进行比较时，这将非常有用。 - JPM

在Chrome浏览器中，链接的源参考被标记为包含恶意软件。 - superjos

Answer 2

这是一个集合差。一个简单的实现方式是：

jQuery.grep(array1, function(el)
                    {
                        return jQuery.inArray(el, array2) == -1;
                    });

这是O(m * n)的时间复杂度，其中m和n是数组的大小。你可以使用哈希集合将其优化为O(m + n)的时间复杂度。对于字符串，你可以使用JavaScript对象作为简单的哈希集合。对于相对较小的数组，以上方法应该已经足够。

- Matthew Flaschen

---

请考虑更新这个答案，使用Array.prototype.filter而不是jQuery.grep，因为它将提供一个解决方案，即使不允许使用jQuery。 - Benjamin Gruenbaum

Array.prototype.filter 确实是一个无需使用库的替代方案。但是，你还需要 Array.prototype.indexOf（而不是 inArray）。然而，这两者都需要在旧浏览器中加载 polyfill（在链接中提供）以实现广泛兼容性。由于问题允许使用 jQuery，因此我选择了它，因为它有自己的 polyfill。 - Matthew Flaschen

Answer 3

我知道一种经过证明的快速解决方案，就是在对其中一个数组进行排序后使用二分查找。因此，该解决方案的时间取决于排序算法，但至少为log(N)。

- akonsu