Saltar al contenido

Los k escuadrones más débiles

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

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

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

¿Lo que te frena es la idea y no el código? Los top-k elementos lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio