Hedefe en yakın k değer
Görev tanımı
Problem
Sırasız bir nums tam sayı listesi, bir target ve bir k sayısı verildiğinde, hedefe en yakın k değeri döndür. İki değer eşit uzaklıktaysa küçük değer daha yakındır. Seçilen değerleri artan sırada döndür.
Örnekler
Input: nums = [9, 2, 14, 5, 7, 11], target = 8, k = 3
Output: [5, 7, 9]
Neden: 7 ve 9 1 uzakta, sonra 5 ve 11 3'te eşit ve küçük değer kazanır
Input: nums = [1, 10, 4, 4], target = 4, k = 2
Output: [4, 4]
Neden: tekrar eden değerler ayrı sayılır
Input: nums = [3], target = 100, k = 1
Output: [3]
Neden: edge case: tek değer ne kadar uzak olursa olsun en yakın olandır
İpuçları
0 / 3
Uzaklığa göre sıralamak n log n'de işe yarar. Yalnız k değere ihtiyacın var; listeyi bir kez okurken neyi tutacağını düşün.
Şimdiye kadar görülen en yakın k değeri, en uzakları kolayca erişilebilir olacak şekilde tut. Yeni bir değer ancak o en uzaktakinden yakınsa önemlidir.
Her değeri k boyutunda bir min-heap'te (negatiflenmiş uzaklık, negatiflenmiş değer) olarak sakla; böylece tutulan en uzak değer, eşitlikte de büyüğü, kökte oturur. Yeni bir eleman kökten büyük karşılaştırıldığında kökü değiştir, sonra hayatta kalanları sırala.
- Hedef zaman
- O(n log k)
- Hedef alan
- O(k)
Çözüm
Bu, bir doğru üzerindeki en yakın k nokta: uzaklık tek bir mutlak farktır, k boyutundaki heap de en iyi k adayı en kötüsü kökte, çıkarılmaya hazır halde tutar. Hem uzaklığı hem değeri negatiflemek Python'un min-heap'ini o max-heap'e çevirir ve eşitlik kuralını karşılaştırmaya katar, çünkü eşitlikte büyük değer daha kötü adaydır. Yeni bir değer kökü yalnız elemanı büyükse, yani daha yakınsa ya da eşit yakın ve daha küçükse değiştirir. Zaman O(n log k), heap O(k) alan kullanır; liste uzun bir akış (stream) ve k küçük olduğunda bu önemli.
import heapq
def closest_k(nums, target, k):
heap = [] # k closest so far, the worst at the root
for x in nums:
entry = (-abs(x - target), -x) # farther, then larger, is worse
if len(heap) < k:
heapq.heappush(heap, entry)
elif entry > heap[0]: # closer than the worst kept value
heapq.heapreplace(heap, entry)
return sorted(-x for _, x in heap)
print(closest_k([9, 2, 14, 5, 7, 11], 8, 3)) # -> [5, 7, 9]
print(closest_k([1, 10, 4, 4], 4, 2)) # -> [4, 4]
print(closest_k([3], 100, 1)) # -> [3]Kodda değil de fikirde mi takıldın? K Closest Points bunu anlatıyor.