Intersection of Two Arrays

Q: İki Dizinin Kesişiminin zaman karmaşıklığı nedir?

Bir hash kümesiyle ortak değerleri bulmak ortalama O(n + m) zaman alır ve yanıttaki k değeri sıralamak O(k log k) ekler; küme O(n) alan kullanır. Her iki diziyi sıralayıp iki işaretçiyle üzerinde ilerlemek O(n log n + m log m) zaman alır. Her çifti karşılaştırmak O(n × m) zaman alır.

KolayHashing

+10

İki tam sayı dizisi alırsın: nums1 ve nums2. Her iki dizide de bulunan tüm değerleri artan sırada döndür. Ortak olan her değer, dizilerden herhangi birinde kaç kez tekrarlanırsa tekrarlansın, yanıtta bir kez yer alır.

Fonksiyon

intersection(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: ilk tamsayı listesi
nums2integer-array: ikinci tamsayı listesi
Döndürürinteger-array: her iki listede bulunan değerler, her biri bir kez, artan sırayla

Kısıtlar

1 ≤ nums1.length, nums2.length ≤ 5000
-10⁵ ≤ nums1[i], nums2[i] ≤ 10⁵
Her iki dizide de en az bir değer bulunur.

Örnekler

Girdi: nums1 = [6, 2, 9, 2, 4]nums2 = [4, 4, 1, 6]
Çıktı: [4, 6]
Açıklama: 4 ve 6 her iki dizide de bulunur. 4, nums2 içinde iki kez görünür ancak bir kez listelenir; 2 ve 9 ise nums2 içinde hiç görünmez.

Girdi: nums1 = [-3, 0, 7]nums2 = [7, -3, -3, 5]
Çıktı: [-3, 7]
Açıklama: -3 ve 7 her iki dizide de bulunur. Artan sırada önce -3 gelir; nums2 içinde önce 7 gelmesine rağmen.

Gönderirken +16 gizli test

Ek soru

Ya nums1 10 değer içeriyorsa ve nums2 zaten sıralanmış bir milyon değer içeriyorsa ne olur? Hangi yaklaşımı seçerdin ve ikili arama, baştan sona taramadan daha hızlı olabilir mi?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Bu problemi iki ayrıntı belirler: her iki tarafta da yinelenen bir değer yanıtta yalnızca bir kez yer alır ve yanıt sıralı olmalıdır. Her çifti karşılaştırmak işe yarar ama n × m karşılaştırma gerektirir; her iki dizi de 5000 değer içerdiğinde bu sayı 2.5 × 10^7 olur. Her iki diziyi de sıralamak, iki işaretçinin ortak değerlerle sıralı biçimde karşılaşmasını sağlar; dizilerden biri için oluşturulan bir hash kümesi ise "bu değer nums1 içinde mi?" sorusunu sabit zamanda yanıtlar.

Her çifti karşılaştırın

Doğru, ama en büyük testlerde bitmiyor

Sezgi

nums1 içindeki her değeri alın ve onu nums2 içinde arayın. İlk eşleşmede aramayı durdurun ve yanıtta zaten bulunan bir değeri atlayın; böylece [8, 8, 8, 8] ile [8, 8] karşılaştırıldığında dört değil, tek bir 8 elde edilir. Yanıtı en sonunda sıralayın.

Bu yöntem doğrudur; çünkü nums1 içindeki bir değerin herhangi bir kopyası nums2 içinde eşleşme bulduğunda bu değer yanıta eklenir ve atlama işlemi aynı değerin iki kez eklenmesini önler.

Bu yöntem yavaştır; çünkü nums1 içindeki her değer nums2 dizisinin tamamını tarayabilir. Her dizide 5000 değer olduğunda bu, en fazla 2.5 × 10^7 karşılaştırma demektir ve büyük testlerde çoğu değer eşleşme bulmaz; bu nedenle taramaların çoğu sonuna kadar sürer.

Algoritma

Boş bir yanıt listesiyle başlayın.
nums1 içindeki her a değeri için, yanıt listesinde zaten varsa bu değeri atlayın.
Aksi takdirde nums2 listesini tarayın; a değerine eşit olan ilk değerde, a değerini yanıta ekleyin ve taramayı durdurun.
Yanıtı artan düzende sıralayın ve döndürün.

def intersection(nums1, nums2):
    result = []
    for a in nums1:
        if a in result:
            continue
        # Look for a anywhere in nums2.
        for b in nums2:
            if a == b:
                result.append(a)
                break
    result.sort()
    return result

İkisini de sırala, ardından iki işaretçiyle ilerle

Sezgi

Sıralandığında, 1. örnek [2, 2, 4, 6, 9] ve [1, 4, 4, 6] hâline gelir. i işaretçisini ilk dizinin başına, j işaretçisini ikinci dizinin başına koy. Daha küçük değerdeki işaretçi ilerler: Diğer dizide ilerideki tüm değerler en az o kadar büyük olduğundan, bu değer artık başka bir değerle eşleşemez. Her iki işaretçi de aynı değeri gösterdiğinde, bu değer ortaktır; onu ekle ve her iki işaretçiyi de ilerlet.

Örnekte: 2 > 1 olunca j ilerler; her iki 2 de 4'ten küçüktür ve i ilerler; 4 = 4 olunca 4 eklenir; ikinci 4, 6'dan küçüktür ve j ilerler; 6 = 6 olunca 6 eklenir. Her iki tarafta da birkaç kez bulunan bir değer, örneğin [2, 2, 3] ve [2, 2] dizilerindeki 2, birden fazla kez eşleşir; onu eklenen son değerle karşılaştırmak, tek bir kopyanın kalmasını sağlar. Sonuç, ek bir adıma gerek kalmadan sıralı çıkar.

Sıralama O(n log n + m log m) maliyetindedir ve dolaşım O(n + m) sürer; çünkü her adımda en az bir işaretçi ilerler. Çoğu sürüm, O(n + m) bellek maliyeti olan kopyaları sıralar. Girdileri yeniden sıralayabiliyorsan, C kodunun yaptığı gibi onları yerinde sırala; böylece gereken tek ek bellek yanıt için olur.

Algoritma

Her iki diziyi de sırala.
i = 0 ve j = 0 olarak ayarla.
Her iki işaretçi de kendi dizilerinin içindeyken, daha küçük değerdeki işaretçiyi ilerlet.
Değerler eşitse, değer eklenen son değere eşit olmadığı sürece değeri ekle, ardından her iki işaretçiyi de ilerlet.
Yanıtı döndür.

def intersection(nums1, nums2):
    a = sorted(nums1)
    b = sorted(nums2)
    i, j = 0, 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            i += 1
        elif a[i] > b[j]:
            j += 1
        else:
            # A shared value: keep it once, even if it repeats.
            if not result or result[-1] != a[i]:
                result.append(a[i])
            i += 1
            j += 1
    return result

İlk dizinin hash kümesi

Sezgi

nums1 içindeki her değeri bir hash kümesine ekle. 1. örnekte küme {6, 2, 9, 4} olur: yinelenen 2, eklenirken tekilleşir. Ardından nums2 üzerinde ilerle ve her değeri kümeye sabit zamanda sor. İlk 4 kümede vardır, bu yüzden yanıta eklenir. İkinci 4 eklenmemelidir; bu nedenle eşleştiği anda değeri kümeden çıkar. 1 kümede yoktur, 6 ise vardır; böylece [4, 6] elde edilir.

Eşleşme olduğunda değeri çıkarmak, her değerin yalnızca bir kez yer almasını sağlar: ilk eşleşmesinden sonra değer kümeden silinir, böylece nums2 içindeki sonraki kopyalar kümede hiçbir şey bulamaz. Eklenen her değer iki dizide de bulunur ve ortak her değer, nums2 içindeki ilk kopyası geldiğinde eklenir.

Kümeyi oluşturmak ve üzerinde ilerlemek ortalama olarak O(n + m) zaman alır. Yanıt, nums2 sırasına göre elde edilir; bu yüzden sonunda sıralayın. Yanıtta k ≤ min(n, m) değer bulunur ve sıralama O(k log k) maliyetlidir. C dilinde yerleşik bir küme yoktur; bu nedenle C kodu, değerler sınırlı olduğundan işe yarayan, value + 10^5 ile indekslenen bir bayrak dizisi kullanır.

Algoritma

nums1 değerlerinden bir hash kümesi first oluşturun.
nums2 içindeki her değer için, değer first içinde bulunuyorsa onu yanıta ekleyin ve first kümesinden çıkarın.
Yanıtı artan sırada sıralayın.
Yanıtı döndürün.

def intersection(nums1, nums2):
    first = set(nums1)
    result = []
    for num in nums2:
        if num in first:
            result.append(num)
            # Remove it so a repeat in nums2 is not added twice.
            first.remove(num)
    result.sort()
    return result

Tuzaklar ve uç durumlar

Buradaki yanlış yanıtların çoğu tekrarlanan değerlerden ve çıktının sırasından kaynaklanır.

Bir değer eşleştiği her seferinde eklemek. [2, 2, 3, 3, 3] ve [3, 2, 2] iki ortak değere sahiptir, bu nedenle yanıt [3, 2, 2] değil, [2, 3] olur.
Değerleri bulduğun sırayla döndürmek. Hash kümesinin üzerinden geçiş nums2 dizisini izler; bu nedenle [7, -3] yine de [-3, 7] şeklinde sıralanmalıdır.
Sayıları metin olarak sıralamak. JavaScript'te karşılaştırıcı olmadan kullanılan sort() dizeleri karşılaştırır; bu nedenle [100000, 99] bu sırada kalır. (x, y) => x - y kullanın.
Küme kesişimi kullanıp sıralamayı unutmak. Python'daki set(nums1) & set(nums2) doğru değerleri belirli bir sıra olmadan bulur; bunu sorted içine alın.
Bayrak dizisini ham değeri kullanarak indekslemek. -3 geçerli bir indeks değildir; önce her değere 10^5 ekleyerek kaydırın.

Sıkça sorulan sorular4

İki Dizinin Kesişiminin zaman karmaşıklığı nedir?

Bir hash kümesiyle ortak değerleri bulmak ortalama O(n + m) zaman alır ve yanıttaki k değeri sıralamak O(k log k) ekler; küme O(n) alan kullanır. Her iki diziyi sıralayıp iki işaretçiyle üzerinde ilerlemek O(n log n + m log m) zaman alır. Her çifti karşılaştırmak O(n × m) zaman alır.

Karma kümesi mi yoksa iki işaretçi mi kullanmalısınız?

Diziler sıralanmamışsa ve bellek yeterliyse karma kümesini kullan: en az işi o yapar. Her iki dizi de zaten sıralı geliyorsa ya da bellek kısıtlıysa ve dizileri yerinde sıralayabiliyorsan iki işaretçi kullan. Bu tarama kümeye ihtiyaç duymaz ve sonucu sıralı olarak üretir.

Kesişimde yinelenen değerleri nasıl korursunuz?

Bir değer, her iki dizide de geçtiği sayıda görünmeliyse; yani [3, 1, 3, 3] ve [3, 3] dizileri [3, 3] sonucunu veriyorsa, küme yerine bir sayım eşlemi kullan. nums1 değerlerini say ve nums2 içindeki sayısı sıfırdan büyük olan her değeri ekleyip sayısını azalt. İki işaretçili gezinmede, eklenen son değere yönelik kontrolü kaldır.

Bir dizi belleğe sığmayacak kadar büyük olduğunda kesişimi nasıl bulursun?

Hash kümesini belleğe sığan diziden oluşturun ve büyük diziyi parçalar hâlinde okuyun; her değeri kümeye göre kontrol edip eşleşme olduğunda kümeden çıkarın. Bellek kullanımı küçük dizinin boyutunda kalır. Dizilerden hiçbiri belleğe sığmıyorsa ikisini de diskte sıralayın ve sıralanmış dosyalar üzerinde iki işaretçili tarama yapın.

Python

def intersection(nums1, nums2):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Girdi

nums1 = [6, 2, 9, 2, 4]
nums2 = [4, 4, 1, 6]

Beklenen

[4, 6]

Intersection of Two Arrays

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her çifti karşılaştırın

İkisini de sırala, ardından iki işaretçiyle ilerle

İlk dizinin hash kümesi

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler