İçeriğe geç

En zayıf k ekip

Kolay#top-k#max-heap~20 dk

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

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

Kodda değil de fikirde mi takıldın? Top-k elemanlar bunu anlatıyor.

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