İki listenin ortak değerleri
Görev tanımı
Problem
İki değer listesi verildiğinde, ikisinde de geçen değerleri döndür. Ortak her değer, listelerden biri onu tekrarlasa bile sonuçta bir kez görünür; sonuç da değerlerin ilk listede ilk göründüğü sırayı izler.
Örnekler
Input: a = [1, 2, 2, 1], b = [2, 2]
Output: [2]
Neden: ortak bir değer ne kadar tekrar ederse etsin bir kez raporlanır
Input: a = [4, 9, 5], b = [9, 4, 9, 8, 4]
Output: [4, 9]
Neden: sıra ikinci listeden değil, ilk listeden gelir
Input: a = [1, 2], b = [3]
Output: []
Neden: edge case: listelerin hiç ortak noktası yok
İpuçları
0 / 3
İlk listenin her değerini bütün ikinci listeyle karşılaştırmak doğru cevabı verir ama çok fazla yeniden okumayla. Karşılaştırma başlamadan önce bir kez neyi hazırlayabileceğini sor.
İlk listenin her elemanında sorulan soru ikinci listeye karşı bir üyelik testidir ve tek işi bunu sabit zamanda cevaplamak olan bir yapı var.
İkinci listeyi bir kümeye yükle. İlk listeyi bir kez dolaş ve küme bir değeri içeriyorsa ve onu henüz raporlamadıysan tut. İlk listedeki tekrarlar çıktıda tekrar üretmesin diye raporladıklarını ikinci bir kümede takip et.
- Hedef zaman
- O(n + m)
- Hedef alan
- O(m)
Çözüm
İkinci listeyi bir kümeye (set) yüklemek, n karşılaştırmanın her birini bir tarama yerine sabit zamanlı bir aramaya çevirir. İlk listeyi sırayla dolaşmak çıktı sırasının bedavaya çıkması demektir; zaten raporlanmış değerlerden oluşan ikinci bir küme de sıralama ya da sonradan işleme olmadan tekrarları dışarıda tutar. Zaman ortalamada O(n + m), arama kümesi artı raporlanan değerler için alan O(m).
def shared_values(a, b):
pool = set(b) # membership in b is now a constant-time test
out, reported = [], set()
for x in a:
if x in pool and x not in reported:
out.append(x) # first appearance in a fixes the order
reported.add(x)
return out
print(shared_values([1, 2, 2, 1], [2, 2])) # -> [2]
print(shared_values([4, 9, 5], [9, 4, 9, 8, 4])) # -> [4, 9]
print(shared_values([1, 2], [3])) # -> []Kodda değil de fikirde mi takıldın? Hash tablosu temelleri bunu anlatıyor.