Los k escuadrones más débiles
La misión
Problema
Una plantilla de entrenamiento es una cuadrícula de ceros y unos en la que cada fila es un escuadrón. En cada fila, todos los unos (miembros entrenados) van antes que los ceros (reclutas). El escuadrón i es más débil que el escuadrón j cuando tiene menos unos, o la misma cantidad de unos y un índice menor. Devuelve los índices de los k escuadrones más débiles, empezando por el más débil.
Ejemplos
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é: los conteos son 2, 4, 1, 2 y 5, y el empate entre los escuadrones 0 y 3 se lo lleva el índice menor
Input: roster = [[1, 0], [1, 0], [0, 0]], k = 2
Output: [2, 0]
Input: roster = [[1, 1]], k = 1
Output: [0]
Por qué: caso límite: un solo escuadrón es el más débil por defecto
Pistas
0 / 3
Ordenar todos los escuadrones por fuerza funciona, pero solo necesitas k de ellos. ¿Qué guardarías si la plantilla fuera demasiado larga para ordenarla?
Guarda los k escuadrones más débiles vistos hasta ahora en un heap organizado para que el más fuerte de ellos quede en la cima. Un escuadrón nuevo solo importa si es más débil que el de la cima, y en ese caso lo reemplaza.
Puntúa cada escuadrón como (cantidad de unos, índice). Haz push de los puntajes negados en un min-heap para que el escuadrón más fuerte que guardas quede en la raíz, reemplaza la raíz cuando llegue un escuadrón más débil y, al final, ordena los k sobrevivientes empezando por el más débil.
- Tiempo objetivo
- O(m · n + m log k)
- Espacio objetivo
- O(k)
Restricciones
- cells are 0 or 1
- in every row all 1s come before all 0s
Solución
Los k escuadrones más débiles son una selección top-k, así que basta con un heap (montículo) de tamaño k: guarda los escuadrones más débiles vistos hasta ahora, con el más fuerte de ellos en la raíz, que es el próximo en ser desalojado. El heapq de Python es un min-heap, así que cada escuadrón se guarda como su par (conteo, índice) negado, lo que convierte al escuadrón más fuerte en la entrada más pequeña. Un escuadrón nuevo reemplaza la raíz solo cuando su par es menor que el de la raíz, que es exactamente la regla de “más débil que”, incluido el desempate por índice. Contar una fila toma O(n) para n columnas, así que el tiempo es O(m · n + m log k) para m escuadrones, y el heap usa O(k) de espacio. Como cada fila está ordenada, el conteo también podría salir de una búsqueda binaria del primer 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]¿Lo que te frena es la idea y no el código? Los top-k elementos lo explica.