Yakut - örneğin, orada iki diziler, ve ben ikisi için yaygın değildir unsurları bulmalıyız - İki dizinin

Question

Ben şu sorunun düşünüyordum için yaygın değil elemanı bulun:

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

Ve beklenen cevap [3].

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

Ama bu bana O(N ** 2) zaman karmaşıklığı verir:

Şimdiye kadar ben böyle yapıyorum.

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

: Ayrıca, ben 2 dizilerin ortak öğeleri) verir & bazı yöntem tersini kullanarak (böyle şekilde onu alma hakkında düşünüyordum)

; ben daha hızlı yapılabilir eminim

başka yolu da, iki diziyi ekleyip uniq benzer bazı yöntemi ile eşsiz maddeyi bulmak için olabilir, böylece: @iamnotmaynard belirtildiği gibi

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

Answer 1

en basit (yer ve stok dizi yöntemlerinde zaten sadece dizileri kullanarak açısından zaten) çözümü differences ait union geçerli:

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

Bu veya O(n**2) daha iyi olabilir veya olmayabilir. Daha iyi performans sunma olasılığı olan başka seçenekler de vardır (diğer cevaplara/yorumlara bakınız).

Düzenleme: İşte sıralama ve yinelemeli yaklaşımın hızlı bir şekilde uygulanması (bu, hiçbir dizinin yinelenen öğeye sahip olmadığını varsayar; aksi takdirde, bu durumda hangi davranışın isteneceğine bağlı olarak değiştirilmesi gerekir). Herhangi biri bunu yapmak için daha kısa bir yol bulabilirse, ilgilenirim. Sınırlayıcı faktör kullanılan türdür. Ruby'nin bir çeşit Quicksort kullandığını, O(n log n)'un en kötü ihtimalle O(n**2) olası en kötü durumlarını kullandığını farz ediyorum; diziler zaten sıralı ise, o zaman tabii ki sort çağrıları kaldırılabilir ve O(n) içinde çalışacaktır.

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

yorumlar, bu geleneksel olarak ayarlanmış bir işlemdir (simetrik fark olarak adlandırılır). Ruby'nin Seti sınıfı bu işlemi kapsamaktadır, bu nedenle en deyimsel yolu bir Set ile olacağını ifade etmek: O (n) performansı vermelidir

Set.new(a)^b 

(set üyelik testinde beri sürekli zamanlı).

Answer 4

Dizi sapmaya bağlı çözüm gibidir:

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

Ayrıca bir blog yazısı okuyabilir yaklaşık Array coherences