EDİT: Herkes bu soruya yeni bir cevap ne olup bittiğini açıklayan attılar. Kabul cevabı en iyi cevap olarak daha fazla bilgi için gönderildi, ama lütfen benim cevaba bakınız hissediyorum.

NOTBu sorun ilk yarı ve kullanılan listeler. Java ve diziler için buna adapte oluyorum. Yani Java-özel numara (ya da bu konuda herhangi bir dilde hileler!) kullanan herhangi bir çözüm görmek isterim olsa da, asıl sorun dilden bağımsız olduğunu unutma.

Sorun

Hadi iki sıralı olmayan tamsayı diziler a ve element tekrarı izni ile b olduğunu söylüyorlar. Aynı alan unsurları bakımından ()hariçdiziler ekstra bir öğe vardır. Örnek olarak:

int[] a = {6, 5, 6, 3, 4, 2};
int[] b = {5, 7, 6, 6, 2, 3, 4};

Giriş olarak bu iki dizi alır ve tek benzersiz tamsayı çıkaran bir algoritma (yukarıdaki durum, 7) tasarım.

Çözüm (Şimdilik)

Ben bu ile geldi:

public static int getUniqueElement(int[] a, int[] b) {
    int ret = 0;
    for (int i = 0; i < a.length; i  ) {
        ret ^= a[i];
    }
    for (int i = 0; i < b.length; i  ) {
        ret ^= b[i];
    }
    return ret;
}

"Resmi sınıfta sunulan" çözüm:

public static int getUniqueElement(int[] a, int[] b) {
    int ret = 0;
    for (int i = 0; i < a.length; i  ) {
        ret  = a[i];
    }
    for (int i = 0; i < b.length; i  ) {
        ret -= b[i];
    }
    return Math.abs(ret);
}

Çok, hem kavramsal olarak aynı şeyi yapıyor. a uzunluk m ve b uzunluk n olduğu göz önüne alındığında, her iki çözüm de O zaman(m, n) çalışan var.

Soru

Daha sonra öğretmenimle konuşmaya başladık ve bir dahi olduğunu ima ettidaha hızlıbunu yapmanın bir yolu. Gerçekten anlamıyorum; bir unsur olup olmadığını öğrenmek içinbenzersiz en azından her öğe bakmak gerekecek gibi görünüyor. En azından O(m n)...değil mi?

Yani daha hızlı bir yolu var mı? Ve eğer öyleyse, ne kadar?

Bu muhtemelen Java içinde yorum HotLick önerisi kullanarak yapabileceğiniz en hızlısıdır. b.length == a.length 1 b ekstra "" element. eşsiz büyük dizi olduğunu farz eder

public static int getUniqueElement(int[] a, int[] b) {
    int ret = 0;
    int i;
    for (i = 0; i < a.length; i  ) {
        ret = ret ^ a[i] ^ b[i];
    }
    return ret ^ b[i];
}

Varsayım yapılamaz bile, kolayca ya da bir b benzersiz elemanı ile daha büyük dizi olduğu davaya dahil ederek genişletebilirsiniz. Hala O(m n) olsa ve atama yükü azalır/tek döngü.

Düzenleme:

Dil uygulama ayrıntıları nedeniyle, bu hala (şaşırtıcı) CPython bunu yapmak için en hızlı yoludur.

def getUniqueElement1(A, B):
    ret = 0
    for a in A: ret = ret ^ a
    for b in B: ret = ret ^ b
    return ret

timeit modülü ile bu test ve bazı ilginç sonuçlar buldum. 16 ** uzun gerçekten steno ret ^= a Python daha hızlı olduğu ortaya çıktı. Ayrıca bir döngü unsurları üzerinden yineleme çok dizinler üzerinden yineleme ve sonra Python indis işlemleri yapmak çok daha hızlı olur. Bu kod Java kopyalamaya çalıştığımda çok daha hızlı benim önceki yöntem daha.

Hikayenin ahlaki bir sorun ve sahte zaten çünkü doğru cevap yok sanırım. OP başka bir cevap aşağıda belirtildiği gibi, bu konuda gerçekten O(m n) ve öğretmeni sadece kendi işletiyormuş daha hızlı gidemezsin çıkıyor. Böylece sorun iki dizini içindeki tüm öğeler üzerinde yineleme için en hızlı yolu bulmak ve hepsinin XOR biriken azaltır. Ve bu demek oluyor tamamen bağımlı dil uygulama ve yapman gereken bazı test ve oynamak için gerçek "hızlı" çözüm ne olursa olsun uygulama kullanıyorsunuz, çünkü genel algoritma değil değiştirin.