İçeriğe geç

Farkı en küçük çiftler

Kolay#sort-first#adjacent-scan~15 dk

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

Hedef zaman
O(n log n)
Hedef alan
O(n)

Kısıtlar

  • 2 ≤ nums.length ≤ 10⁵
  • values are distinct integers

Kodda değil de fikirde mi takıldın? Hangi sıralama ne zaman? bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case