En yakın tekrar mesafesi
Görev tanımı
Problem
Sana bir değer listesi veriliyor. Aynı değeri tutan bütün konum çiftleri arasında birbirine en yakın duran çifti bul ve aralarındaki boşluğu, indekslerinin farkı olarak ölçülmüş halde döndür. Hiçbir değer iki kez görünmüyorsa -1 döndür.
Örnekler
Input: values = [7, 1, 3, 7, 1, 7]
Output: 2
Neden: 3 ve 5 indekslerindeki 7'ler iki uzakta; 1'ler üç uzakta
Input: values = [3, 8, 8, 3]
Output: 1
Neden: iki 8 yan yana duruyor
Input: values = [5, 6, 7]
Output: -1
Neden: edge case: hiçbir şey tekrar etmiyor
İpuçları
0 / 3
Her konum çiftini karşılaştırmak işe yarar ama iş uzunluğun karesiyle büyür: listeyi ikiye katla, dört kat uzun sürer.
Mevcut konumdaki değer için en küçük boşluğu yalnız tek bir önceki konum verebilir. Hangisi ve onu anında bulmanı ne sağlar?
Listeyi bir kez dolaş; her değerden onu en son gördüğün indekse giden bir map tut. Mevcut değer zaten map'teyse mevcut indeks eksi saklanan indeksi şimdiye kadarki en iyi boşlukla karşılaştır, sonra saklanan indeksin üzerine yaz.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Çözüm
Herhangi bir konumun en yakın önceki ikizi en sonuncusudur; bu yüzden her değerin yalnız son indeksini hatırlamak yeter. Bir hash map bu aramayı ortalamada sabit zamanda cevaplar; bu da karesel çift kontrolünü tek bir geçişe çevirir. Map her adımdan sonra güncellenir, böylece her zaman her değerin en son indeksini tutar. Zaman ortalamada O(n), map için alan O(n).
def closest_repeat(values):
last_seen = {} # value -> most recent index
best = -1
for i, v in enumerate(values):
if v in last_seen:
gap = i - last_seen[v]
if best == -1 or gap < best:
best = gap
last_seen[v] = i # only the latest index can matter later
return best
print(closest_repeat([7, 1, 3, 7, 1, 7])) # -> 2
print(closest_repeat([3, 8, 8, 3])) # -> 1
print(closest_repeat([5, 6, 7])) # -> -1Kodda değil de fikirde mi takıldın? Big-O nedir? bunu anlatıyor.