Ruby - 查找两个数组中不共有的元素

Question

我在思考一个问题：有两个数组，我需要找到它们之间不共同的元素，例如：

a = [1,2,3,4]
b = [1,2,4]

我将期望的答案翻译为[3]。

迄今为止，我一直是这样做的：

a.select { |elem| !b.include?(elem) }

但它给出了O(N ** 2)的时间复杂度。我确信可以更快地完成它 ;)

另外，我一直在思考如何将其获取为此类形式（使用某种与&相反的方法，它给出了2个数组的公共元素）：

a !& b  #=> doesn't work of course

另一种方法可能是将两个数组相加，并使用类似于uniq的某种方法查找唯一元素，使其变为：

[1,1,2,2,3,4,4].some_method #=> would return 3

- Jacka

---

(a-b) | (b-a) # => [3] 意思是取两个集合 a-b 和 b-a 的并集，得到的结果是包含元素 3 的数组。请参考 http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-2D ，注意这个运算不满足交换律，即通常情况下 a-b != b-a。 - Reinstate Monica -- notmaynard

应该是：(a-b) | (b-a) - Shawn Balestracci

@ShawnBalestracci 没错，你说得对。我甚至在我的测试控制台中正确地编写了它，但是后来错误地重写了它。 - Reinstate Monica -- notmaynard

这取决于Ruby的实现方式，也就是说，我不知道。数组也可以转换为 Sets，然后使用 Set#^ 函数，因为它使用哈希表，所以时间复杂度可能是 O(n log n) 或 O(n)。 - Reinstate Monica -- notmaynard

或者对数组进行排序（应该是O（n log n）），然后遍历这两个数组，将只在一个数组中的元素添加到结果数组中（O（n））。 - Reinstate Monica -- notmaynard

Answer 1

最简单的解决方案（以使用已经存在的数组和库存数组方法为基础），是采用合并 差异：

a = [1,2,3,4]
b = [1,2,4]
(a-b) | (b-a)
=> [3]

这可能比 O(n**2) 好，也可能不如其他可提供更好性能的选项（请参见其他答案/评论）。

编辑：这是一种较快的排序和迭代方法的实现（假设没有数组有重复的元素；否则需要根据所需的行为进行修改）。如果有人能想出更短的方法来做到这一点，我会很感兴趣。限制因素是所使用的排序算法。我假设 Ruby 使用某种快速排序，因此复杂度平均为 O(n log n)，最坏情况可能为 O(n**2)；如果数组已经排序，则可以删除两个调用 sort 并以 O(n) 运行。

def diff a, b
  a = a.sort
  b = b.sort
  result = []
  bi = 0
  ai = 0
  while (ai < a.size && bi < b.size)
    if a[ai] == b[bi]
      ai += 1
      bi += 1
    elsif a[ai]<b[bi]
      result << a[ai]
      ai += 1
    else
      result << b[bi]
      bi += 1
    end
  end
  result += a[ai, a.size-ai] if ai<a.size
  result += b[bi, b.size-bi] if bi<b.size
  result
end

- Reinstate Monica -- notmaynard

---

使用下划线，对差集进行合并！感谢您的支持！result = _.union(_.difference(a, b), _.difference(b, a)); - BuffMcBigHuge

Answer 2

正如 @iamnotmaynard 在评论中指出的那样，这通常是一个集合操作（称为对称差）。Ruby 的 Set 类包括此操作，因此最惯用的表达方式是使用 Set：

Set.new(a) ^ b

那应该会提供O(n)的性能（因为集合成员测试是常数时间）。

- Chuck

Answer 3

a = [1, 2, 3]
b = [2, 3, 4]
a + b - (a & b)
# => [1, 4]

- sawa

---

哪一个更好？这个还是被接受的解决方案？ - Donato

从垃圾回收的角度来看，这个解决方案更好（禁用GC后，total_allocated_object的值会减少）。 - Anatoly

Answer 4

数组发散的解决方案如下：

a = [1, 2, 3]
b = [2, 3, 4]
(a - b) | (b - a)
# => [1, 4]

您还可以阅读我的博客文章关于数组的相关性

- Christian Rolle