Set Matrix Zeroes
La entrada es una cuadrícula m × n de números enteros, proporcionada fila por fila, así que matrix[i][j] está en la fila i y la columna j. Dondequiera que la cuadrícula tenga un 0, establece toda esa fila y toda esa columna en 0. Solo cuentan los ceros que están presentes al principio: una celda que cambies a 0 no pone a cero su propia fila ni su propia columna. Puedes modificar la cuadrícula en el mismo lugar; devuélvela.
Función
- matrixinteger-2d-array
- la cuadrícula de números enteros, una lista interna por fila
- Devuelveinteger-2d-array
- la matriz con cada fila y cada columna que contenían un 0 establecidas en 0
Restricciones
m == matrix.lengthyn == matrix[i].length1 ≤ m, n ≤ 1000ym × n ≤ 5000- 모든
mfilas contienennvalores. -1000 ≤ matrix[i][j] ≤ 1000
Ejemplos
- Entrada
- matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
- Salida
- [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
- Explicación
- El único 0 está en la fila 1, columna 1. La fila 1 queda llena de ceros, y lo mismo ocurre con la columna 1, lo que convierte el 8 y el 6 en 0. Las cuatro esquinas no están en ninguna de las dos líneas y conservan sus valores.
- Entrada
- matrix = [[0, 4, 2, 0], [9, 3, 5, 1], [6, 1, 0, 8]]
- Salida
- [[0, 0, 0, 0], [0, 3, 0, 0], [0, 0, 0, 0]]
- Explicación
- Los ceros de la fila 0 (columnas 0 y 3) y de la fila 2 (columna 2) despejan las filas 0 y 2 y las columnas 0, 2 y 3. La fila 1 conserva su 3 en la columna 1: los ceros que escribes no se propagan.
Para ir más allá
El mejor enfoque de abajo mantiene dos valores booleanos adicionales. ¿Puedes arreglártelas con uno, haciendo que matrix[0][0] represente la primera fila?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Intenta borrar una fila y una columna en cuanto encuentres un 0, en el primer ejemplo. ¿Por qué desaparecen tres de las cuatro esquinas?
Una celda termina siendo 0 exactamente cuando su fila o su columna contenía un 0 al principio. Registra esas filas y columnas en una primera pasada que solo lee; después, escribe en una segunda pasada.
Con espacio extra O(1), mantén las marcas dentro de la matriz: la primera columna tiene una celda por fila y la primera fila, una celda por columna. Antes de usarlas, anota en dos booleanos si la primera fila y la primera columna contienen un 0 propio, y límpialas al final.
Solución
Un 0 que escribes tiene exactamente el mismo aspecto que un 0 que ya estaba ahí, así que borrar líneas durante el recorrido propaga ceros por toda la matriz. Separa la lectura de la escritura: primero registra qué filas y columnas contenían un 0 y después bórralas. Guarda ese registro en dos arreglos o, para usar O(1) de espacio adicional, en la primera fila y la primera columna de la propia matriz.
Marca filas y columnas en dos arreglos
Intuición
Una celda acaba siendo 0 exactamente cuando su fila o su columna contenía un 0 al principio. Así que registra dos listas de datos, zeroRow[i] y zeroCol[j], en un recorrido que nunca escribe; después, borra cada celda cuya fila o columna esté marcada. Nada se propaga, porque todas las lecturas se realizan antes de la primera escritura.
Cada recorrido visita las m·n celdas una vez, así que el tiempo es O(m·n), y los arreglos contienen m + n valores booleanos.
Algoritmo
- Crea
zeroRowcon m elementos yzeroColcon n elementos, todos false. - Recorre cada celda. Cuando
matrix[i][j]sea 0, establecezeroRow[i]yzeroCol[j]en true. - Vuelve a recorrer cada celda y establécela en 0 cuando
zeroRow[i]ozeroCol[j]sea true. - Devuelve la matriz.
def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
zero_row = [False] * m
zero_col = [False] * n
# Pass 1: only read, so a new zero can never spread further.
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
zero_row[i] = True
zero_col[j] = True
# Pass 2: write.
for i in range(m):
for j in range(n):
if zero_row[i] or zero_col[j]:
matrix[i][j] = 0
return matrixUsa la primera fila y columna como marcadores
Intuición
La primera columna tiene una celda por fila y la primera fila, una por columna: esas son las formas de los dos arreglos de marcadores. Así, un 0 en la fila i, columna j escribe 0 en matrix[i][0] y matrix[0][j]. Eso no hace perder nada: cada una de esas celdas está en una línea que, de todos modos, debe convertirse en 0.
La fila 0 y la columna 0 son datos además de marcadores, y un marcador allí oculta si ya contenían un 0 propio. Así que compruébalas primero y guarda las respuestas en dos booleanos. Marca y llena solo las celdas con i ≥ 1 y j ≥ 1, y limpia la fila 0 y la columna 0 al final, porque el llenado las lee.
En el segundo ejemplo, el 3 de la fila 1, columna 1 sobrevive porque sus marcadores, matrix[1][0] = 9 y matrix[0][1] = 4, no son 0. El tiempo se mantiene en O(m·n), con dos booleanos de memoria adicional (O(m·n) en R, que primero copia la entrada).
Algoritmo
- Establece
firstRowZerosi la fila 0 contiene un 0 yfirstColZerosi la columna 0 contiene un 0. - Para cada celda con
i ≥ 1yj ≥ 1que contenga 0, establecematrix[i][0]ymatrix[0][j]en 0. - Para cada celda con
i ≥ 1yj ≥ 1, establécela en 0 cuandomatrix[i][0]omatrix[0][j]sea 0. - Si
firstRowZeroes verdadero, establece la fila 0 en 0. SifirstColZeroes verdadero, establece la columna 0 en 0. - Devuelve la matriz.
def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
# The first row and column will hold the markers, so remember first
# whether they need to become zero themselves.
first_row_zero = any(matrix[0][j] == 0 for j in range(n))
first_col_zero = any(matrix[i][0] == 0 for i in range(m))
# Mark: a zero inside the matrix flags its row in column 0
# and its column in row 0.
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# Fill the inside from the markers.
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# The marker row and column go last.
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_zero:
for i in range(m):
matrix[i][0] = 0
return matrix
Errores comunes y casos límite
- Limpiar una fila y una columna en cuanto encuentres un 0. En el primer ejemplo, el nuevo 0 de la fila 1, columna 2 limpia después la columna 2, y solo sobrevive el 3 de la esquina superior izquierda.
- Permitir que
matrix[0][0]marque tanto la fila 0 como la columna 0. En[[1, 2, 3], [0, 5, 6], [7, 8, 9]], el 0 de la columna 0 limpia después erróneamente la fila 0. - Limpiar la fila 0 o la columna 0 antes de rellenar. En
[[0, 2, 3], [4, 5, 6], [7, 8, 9]], todas las columnas parecen marcadas después, y toda la matriz se convierte en 0. - Olvidar las líneas individuales. Con una sola fila, los bucles que empiezan en 1 no hacen nada y los booleanos se encargan de todo:
[[1, 0, 3]]debe convertirse en[[0, 0, 0]].
Preguntas frecuentes3
¿Por qué no puedes establecer los ceros mientras recorres la matriz?
Un 0 que escribas se ve igual que un 0 original. Cuando el escaneo llega a él, borra su propia fila y columna, y esos nuevos ceros se propagan aún más. Registra cada cero original antes de cambiar cualquier celda.
¿Cuál es la complejidad temporal de «Set Matrix Zeroes»?
O(m·n) para una matriz m × n, ya que cada celda se lee y se escribe un número constante de veces. Ninguna solución lo hace mejor, porque cualquier celda omitida podría ser el 0 que cambia la respuesta. El espacio adicional es O(m + n) con arreglos marcadores y O(1) usando la primera fila y la primera columna como marcadores.
¿Puedes marcar las celdas con un valor especial en lugar de 0?
Algunas soluciones escriben un marcador en las celdas que hay que borrar y convierten los marcadores en ceros al final. Eso solo funciona si el marcador nunca puede aparecer en la entrada, algo que una matriz de enteros rara vez garantiza. Escribirlo en una fila y una columna por cada 0 también cuesta O(m·n·(m + n)) de tiempo.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def setZeroes(matrix):
# Escribe el código aquíPrueba #1
Prueba #2
Argumento
matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
Salida Esperada
[[3, 0, 1], [0, 0, 0], [2, 0, 4]]