En zayıf k ekip
Görev tanımı
Problem
Bir eğitim kadrosu, her satırı bir ekip olan 0 ve 1'lerden oluşan bir grid. Her satırda 1'ler (eğitimli üyeler) 0'lardan (acemiler) önce gelir. i ekibi, daha az 1'i varsa ya da aynı sayıda 1'i ve daha küçük bir indeksi varsa j ekibinden zayıftır. En zayıf k ekibin indekslerini en zayıfı önce olacak şekilde döndür.
Örnekler
Input: roster = [[1, 1, 0, 0, 0], [1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [1, 1, 1, 1, 1]], k = 3
Output: [2, 0, 3]
Neden: sayılar 2, 4, 1, 2 ve 5; 0 ve 3 numaralı ekipler arasındaki eşitlik küçük indekse gider
Input: roster = [[1, 0], [1, 0], [0, 0]], k = 2
Output: [2, 0]
Input: roster = [[1, 1]], k = 1
Output: [0]
Neden: edge case: tek ekip varsayılan olarak en zayıftır
İpuçları
0 / 3
Her ekibi güce göre sıralamak işe yarar, ama yalnız k tanesine ihtiyacın var. Kadro sıralanamayacak kadar uzun olsaydı neyi tutardın?
Şimdiye kadar görülen en zayıf k ekibi, en güçlüleri tepede olacak şekilde düzenlenmiş bir heap'te tut. Yeni bir ekip ancak o tepedekinden zayıfsa önemlidir, o zaman da onun yerini alır.
Her ekibi (1'lerin sayısı, indeks) olarak puanla. Tutulan en güçlü ekip kökte otursun diye negatiflenmiş puanları bir min-heap'e push et, daha zayıf bir ekip gelince kökü değiştir ve sonunda hayatta kalan k ekibi en zayıfı önce olacak şekilde sırala.
- Hedef zaman
- O(m · n + m log k)
- Hedef alan
- O(k)
Kısıtlar
- cells are 0 or 1
- in every row all 1s come before all 0s
Çözüm
En zayıf k ekip bir top-k seçimidir, bu yüzden k boyutunda bir heap yeter: şimdiye kadar görülen en zayıf ekipleri, bir sonraki çıkarılacak olan en güçlüleri kökte olacak şekilde tutar. Python'un heapq'su bir min-heap'tir; bu yüzden her ekip negatiflenmiş (count, index) çifti olarak saklanır, bu da en güçlü ekibi en küçük eleman yapar. Yeni bir ekip kökü yalnız çifti kökünkinden küçük olduğunda değiştirir; bu da indekse göre eşitlik bozma dahil tam olarak daha zayıf kuralıdır. n sütun (column) için bir satırı saymak O(n) tutar; m ekip için zaman O(m · n + m log k), heap O(k) alan kullanır. Her satır sıralı olduğu için sayı, ilk 0 için bir ikili aramayla da bulunabilirdi.
import heapq
def k_weakest(roster, k):
heap = [] # k weakest so far, strongest at the root
for i, row in enumerate(roster):
entry = (-sum(row), -i) # negated: heapq keeps the smallest on top
if len(heap) < k:
heapq.heappush(heap, entry)
elif entry > heap[0]: # weaker than the strongest kept squad
heapq.heapreplace(heap, entry)
return [-i for _, i in sorted(heap, reverse=True)]
print(k_weakest([[1, 1, 0, 0, 0], [1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [1, 1, 1, 1, 1]], 3)) # -> [2, 0, 3]
print(k_weakest([[1, 0], [1, 0], [0, 0]], 2)) # -> [2, 0]
print(k_weakest([[1, 1]], 1)) # -> [0]Kodda değil de fikirde mi takıldın? Top-k elemanlar bunu anlatıyor.