Pular para o conteúdo

Os K esquadrões mais fracos

Fácil#top-k#max-heap~20 min

A missão

Problema

Um quadro de treinamento é um grid de 0s e 1s em que cada linha é um esquadrão. Em toda linha, os 1s (membros treinados) vêm todos antes dos 0s (recrutas). O esquadrão i é mais fraco que o esquadrão j quando tem menos 1s, ou o mesmo número de 1s e um índice menor. Retorne os índices dos k esquadrões mais fracos, do mais fraco para o mais forte.

Exemplos

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]
Por quê: as contagens são 2, 4, 1, 2 e 5, e o empate entre os esquadrões 0 e 3 vai para o menor índice
Input:  roster = [[1, 0], [1, 0], [0, 0]], k = 2
Output: [2, 0]
Input:  roster = [[1, 1]], k = 1
Output: [0]
Por quê: edge case: um único esquadrão é o mais fraco por padrão

Dicas

0 / 3

Tempo-alvo
O(m · n + m log k)
Espaço-alvo
O(k)

Restrições

  • cells are 0 or 1
  • in every row all 1s come before all 0s

Travou na ideia, e não no código? Top-k elementos explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado