Ruby - 查找两个数组不相同的元素

Question

我一直在思考以下问题 - 有两个数组，我需要找到它们不常见的元素，例如:

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

预期的答案是[3]。

到目前为止，我一直这样做:

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

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

此外，我一直在考虑以这种方式获取它(使用一些与 & 相反的方法，它给出了 2 个数组的公共(public)元素):

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

另一种方法可能是将两个数组相加并使用类似于 uniq 的方法找到唯一元素，这样:

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

Answer 1

最简单的(就仅使用已经存在的数组和库存数组方法而言)解决方案是 union的 differences :

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