ルビー - そこに2つの配列があり、私はそれらの両方に共通ではない要素を見つける必要があり、例えば - 私は次のような問題について考えてきた二つの配列

Question

のためではない共通の要素を探す：

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

そして、期待される答えは[3]です。

これまでのところ、私はこのようにそれを行ってきた：

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

しかし、それは私にO(N ** 2)時間の複雑さを与えます。

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

：また、私は2つの配列の共通要素）を与える &にいくつかの方法とは反対側を使用して（このように何とかそれを得ることについて考えてきた）

、私はそれがより迅速に行うことができると確信しています

もう一つの方法は、二つの配列を追加し、uniqに似たいくつかの方法でユニークな要素を発見するかもしれないように：@iamnotmaynardがで述べたように

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

Answer 1

（とにかく、唯一既に適所にアレイおよび在庫アレイ方式を使用する点で）最も簡単な解決策は、differencesのunionある：

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

これはかよいO(n**2)よりも良好であってもよいです。他の選択肢もあります（他の回答/コメントを参照）。

編集：sort-and-iterateアプローチのquick-ish実装です（これは配列に繰り返し要素がないことを前提としています;そうでない場合は、その場合にどのような振る舞いが必要かによって変更する必要があります）。誰かがそれを行うための短い方法を考え出すことができるなら、私は興味があるでしょう。制限要因は、使用されるソートです。私はRubyがある種のクイックソートを使用していると仮定しているので、複雑さの平均はO(n log n)で、可能な最悪ケースはO(n**2)です。配列が既にソートされている場合は、もちろんsortへの2つの呼び出しを取り除くことができ、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

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

Answer 3

これは伝統的に集合演算（対称差分と呼ばれます）です。 Rubyの設定クラスは、この操作を含んでいるので、ほとんどの慣用的な方法は、それがセットになり表現するために：O（n）のパフォーマンス与える必要があり

Set.new(a)^b 

（セット・メンバシップのテストからは、一定の時間です）。

Answer 4

配列相違のためのソリューションのようなある：

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

また、およそArray coherences