Os K esquadrões mais fracos
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
Ordenar todos os esquadrões por força funciona, mas você só precisa de k deles. O que você guardaria se o quadro fosse longo demais para ordenar?
Guarde os k esquadrões mais fracos vistos até agora em um heap organizado de modo que o mais forte deles fique no topo. Um esquadrão novo só importa se for mais fraco que esse do topo, e aí ele o substitui.
Dê a cada esquadrão a pontuação (contagem de 1s, índice). Insira as pontuações negadas em um min-heap para que o mais forte dos esquadrões guardados fique na raiz, substitua a raiz quando chegar um esquadrão mais fraco e, no fim, ordene os k sobreviventes do mais fraco para o mais forte.
- 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
Solução
Os k esquadrões mais fracos são uma seleção top-k, então um heap de tamanho k basta: ele guarda os esquadrões mais fracos vistos até agora, com o mais forte deles na raiz, o próximo a ser descartado. O heapq do Python é um min-heap, então cada esquadrão é guardado como o seu par (contagem, índice) negado, o que faz do esquadrão mais forte a menor entrada. Um esquadrão novo só substitui a raiz quando o seu par é menor que o da raiz, que é exatamente a regra de “mais fraco que”, incluindo o desempate por índice. Contar uma linha leva O(n) para n colunas, então o tempo é O(m · n + m log k) para m esquadrões, e o heap usa espaço O(k). Como cada linha é ordenada, a contagem também poderia vir de uma busca binária pelo primeiro 0.
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]Travou na ideia, e não no código? Top-k elementos explica isso.