Karşılıklı takip çiftleri
Görev tanımı
Problem
Bir sosyal uygulama kimin kimi takip ettiğini [a, b] çiftlerinden oluşan bir liste olarak saklıyor; bu, a kişisinin b kişisini takip ettiği anlamına geliyor ve kişiler 0'dan n - 1'e kadar numaralı. Liste aynı çifti birden fazla kez içerebilir ve kimse kendini takip etmez. Birbirini takip eden kaç sırasız kişi çifti olduğunu döndür.
Örnekler
Input: n = 4, follows = [[0, 1], [1, 0], [1, 2], [2, 3], [3, 2], [0, 2]]
Output: 2
Neden: 0 ile 1, 2 ile 3; 1, 2'yi takip ediyor ama tersi değil
Input: n = 3, follows = [[0, 1], [0, 1], [1, 0]]
Output: 1
Neden: tekrar eden çift yine tek bir karşılıklı çifti tarif eder
Input: n = 2, follows = []
Output: 0
Neden: edge case: kimse kimseyi takip etmiyor
İpuçları
0 / 3
a'dan b'ye her takip için soru, b'den a'ya ters takibin var olup olmadığı. Bir graf gösterimi bunu ne kadar hızlı cevaplayabilir?
Bir komşuluk matrisi bunu sabit zamanda cevaplar ama n kare bellek ister. Kişi başına bir komşu kümesi de ortalamada sabit zamanda cevaplar ve yalnız var olan takipleri saklar.
Her kişi için takip edilenlerin bir kümesini kur; bu, tekrar eden çiftleri de atar. Sonra her a kişisi ve a'nın kümesindeki her b için, a b'den küçükse ve a b'nin kümesinde görünüyorsa çifti say.
- Hedef zaman
- O(n + m)
- Hedef alan
- O(n + m)
Kısıtlar
- people are numbered 0 to n - 1
- pairs may repeat
- nobody follows themselves
Çözüm
Her kişinin takiplerini bir küme (set) olarak saklamak, aynı zamanda hızlı bir kenar testi işlevi gören bir komşuluk listesi (adjacency list) verir; bu problemin sürekli sorduğu tek soru da bu. Kümeler tekrar eden çiftleri de emer, bu yüzden bir tekrar asla iki kez sayılamaz. Her karşılıklı çift iki kez, her iki taraftan birer kez görülür; a < b testi de bu görülmelerden tam olarak birini tutar. m takip çifti için ortalamada zaman O(n + m), alan O(n + m).
def mutual_pairs(n, follows):
adj = [set() for _ in range(n)] # adjacency sets: fast edge tests
for a, b in follows:
adj[a].add(b)
count = 0
for a in range(n):
for b in adj[a]:
if a < b and a in adj[b]: # a < b counts each pair once
count += 1
return count
print(mutual_pairs(4, [[0, 1], [1, 0], [1, 2], [2, 3], [3, 2], [0, 2]])) # -> 2
print(mutual_pairs(3, [[0, 1], [0, 1], [1, 0]])) # -> 1
print(mutual_pairs(2, [])) # -> 0Kodda değil de fikirde mi takıldın? Liste mi, matris mi bunu anlatıyor.