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

Answer 1

最简单的(在只使用阵列已经到位和股票阵列方法,反正方面)的解决方案是联合的差异:

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

这可能会或可能不会更好O(n**2).还有其他选择可能会提供更好的表现(见其他答案/评论).

编辑:这是一个快速实现的排序和迭代方法(假设没有数组有重复的元素;否则需要根据在这种情况下需要的行为进行修改).如果有人能想出一个更短的方法来做,我会感兴趣.限制因素是使用的排序.我假设Ruby使用某种Quicksort,因此复杂度平均值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

Answer 2

正如@iamnotmaynard在评论中指出的那样,传统上这是一种集合操作(​​称为对称差异).Ruby的Set类包含了这个操作,因此表达它的最惯用的方法是使用Set:

Set.new(a) ^ b

这应该给出O(n)性能(因为集合成员资格测试是恒定时间).

Answer 3

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