紅寶石 - 尋找元素不常見的兩個數組

我一直在思考如下問題 - 有兩個數組，我需要找到的元素並不常見他們兩個，例如：紅寶石 - 尋找元素不常見的兩個數組

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

來源

2013-11-25 Jacka

'（A-B）| （ba）＃=> [3]'見http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-2D並注意它不是可交換的，即通常'ab ！= ba' – iamnotmaynard

那應該是：（ab）| （b-a） –

@ShawnBalestracci你是對的。我甚至在我的測試控制檯中正確寫入了它，但將其重寫錯誤。 – iamnotmaynard

最簡單的（以在適當位置和股票陣列方法已經僅使用陣列而言，無論如何）溶液是differences的union：

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

這可能會或可能不會比O(n**2)更好。還有其他選擇可能會提供更好的性能（請參閱其他答案/評論）。

編輯：下面是sort-and-iterate方法的一個快速實現（假定沒有數組有重複的元素;否則需要根據在這種情況下需要的行爲進行修改）。如果任何人都可以想出一個更短的方式來做到這一點，我會感興趣。限制因素是使用的排序。我假設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

來源

2013-11-25 23:31:27 iamnotmaynard

聯盟的區別！感謝那！使用下劃線： 'result = _.union（_。difference（a，b），_.difference（b，a））;'' – BuffMcBigHuge

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

來源

2013-11-25 23:09:22 sawa

哪一個是可取的？這還是被接受的解決方案？ – Donato

從垃圾收集的角度來看，此解決方案更好（您可以在禁用GC時看到** total_allocated_object **的值較小）。 – Anatoly

由於@iamnotmaynard中指出評論，這通常是一個集合操作（稱爲對稱差異）。 Ruby的集合類包括這種操作，所以最地道的表達方式將是一個集：

Set.new(a)^b

這應該給O（n）性能（因爲一組成員資格測試是恆定的時間）。

來源

2013-11-25 23:19:53 Chuck

數組分歧的解決方法是這樣的：

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

您還可以閱讀博客帖子大約Array coherences

來源

2016-10-25 18:58:21

紅寶石 - 尋找元素不常見的兩個數組

回答

相關問題