Ruby - Найти элемент, не являющийся общим для двух массивов

Я думал о следующей проблеме: есть два массива, и мне нужно найти элементы, не общие для них обоих, например:

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

Ответ 1

Самый простой (с точки зрения использования только массивов, уже существующих и методов массива), является union различия:

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

Ответ 2

Как отмечалось в комментариях, это традиционно представляет собой заданную операцию (называемую симметричной разностью). Класс Ruby Set включает эту операцию, поэтому самый идиоматический способ выразить это будет с помощью Set:

Set.new(a) ^ b

Это должно дать производительность O (n) (поскольку установленный критерий членства является постоянным).

Ответ 3

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

Ответ 4

Решение для расходимостей Array выглядит так:

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

Вы также можете прочитать сообщение в блоге о Согласования массивов