Farkı en küçük çiftler
Görev tanımı
Problem
Bir zamanlama servisi olay zaman damgalarını kaydediyor ve birbirine en yakın zamanda olan olay çiftlerini istiyor. Birbirinden farklı en az iki tam sayıdan oluşan bir liste verildiğinde, herhangi ikisi arasındaki en küçük mutlak farkı bul ve o farka sahip a < b olan her [a, b] çiftini a'ya göre artan sırada listeleyerek döndür. Listede en fazla 100.000 değer var, bu yüzden her çifti kontrol etmek çok yavaş.
Örnekler
Input: nums = [4, 2, 1, 3]
Output: [[1, 2], [2, 3], [3, 4]]
Neden: en küçük fark 1 ve üç çiftte var
Input: nums = [3, 8, -10, 23, 19, -4, -14, 27]
Output: [[-14, -10], [19, 23], [23, 27]]
Input: nums = [1, 3, 6, 10, 15]
Output: [[1, 3]]
Neden: edge case: en küçük fark yalnız bir çiftte var
İpuçları
0 / 3
Her çifti karşılaştırmak karesel. Sıraladıktan sonra hangi çiftler en yakın olabilir?
Sıralı bir listede herhangi bir değerin en yakın eşi komşularından biridir; daha uzaktaki her şey en az o kadar uzaktır.
Sırala, sonra komşu çiftleri iki kez tara: bir kez en küçük farkı bulmak için, bir kez de o farka sahip her çifti toplamak için. Çiftler a'ya göre bedavaya sıralı çıkar.
- Hedef zaman
- O(n log n)
- Hedef alan
- O(n)
Kısıtlar
- 2 ≤ nums.length ≤ 10⁵
- values are distinct integers
Çözüm
Soru birbirine yakın değerlerle ilgili olduğunda sıralama doğru araçtır, çünkü yakın değerleri yan yana koyar. Sıralı bir listede bir değer ile sonraki herhangi bir değer arasındaki fark en az hemen komşusuna olan fark kadardır; bu yüzden yalnız n - 1 komşu çiftin kontrol edilmesi gerekir. Bir tarama en küçük farkı bulur, ikincisi de ona sahip çiftleri zaten artan sırada toplar. Sıralama baskındır; zaman O(n log n), sıralı kopya ve cevap için ek alan O(n).
def smallest_gap_pairs(nums):
s = sorted(nums)
best = min(b - a for a, b in zip(s, s[1:])) # only neighbours can win
return [[a, b] for a, b in zip(s, s[1:]) if b - a == best]
print(smallest_gap_pairs([4, 2, 1, 3])) # -> [[1, 2], [2, 3], [3, 4]]
print(smallest_gap_pairs([3, 8, -10, 23, 19, -4, -14, 27])) # -> [[-14, -10], [19, 23], [23, 27]]
print(smallest_gap_pairs([1, 3, 6, 10, 15])) # -> [[1, 3]]Kodda değil de fikirde mi takıldın? Hangi sıralama ne zaman? bunu anlatıyor.