Set Matrix Zeroes

Q: Quelle est la complexité temporelle de Set Matrix Zeroes ?

O(m·n) pour une matrice m × n , puisque chaque cellule est lue et écrite un nombre constant de fois. Aucune solution ne fait mieux, car toute cellule ignorée pourrait être le 0 qui change la réponse. L’espace supplémentaire est de O(m + n) avec des tableaux marqueurs et de O(1) en utilisant la première ligne et la première colonne comme marqueurs.

MoyenTableaux et chaînes Hachage

+10

L’entrée est une grille m × n d’entiers, donnée ligne par ligne ; ainsi, matrix[i][j] se trouve à la ligne i et à la colonne j. Partout où la grille contient un 0, mettez toute la ligne et toute la colonne correspondantes à 0. Seuls les zéros présents au départ comptent : une cellule que vous transformez en 0 n’efface pas sa propre ligne ni sa propre colonne. Vous pouvez modifier la grille sur place ; renvoyez-la.

Fonction

setZeroes(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: la grille d’entiers, une liste interne par ligne
Renvoieinteger-2d-array: la matrice avec chaque ligne et chaque colonne qui contenait un 0 mises à 0

Contraintes

m == matrix.length et n == matrix[i].length
1 ≤ m, n ≤ 1000 et m × n ≤ 5000
Toutes les lignes m contiennent n valeurs.
-1000 ≤ matrix[i][j] ≤ 1000

Exemples

Entrée: matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
Sortie: [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
Explication: Le seul 0 se trouve à la ligne 1, colonne 1. La ligne 1 devient entièrement composée de zéros, tout comme la colonne 1, ce qui transforme le 8 et le 6 en 0. Les quatre coins ne se trouvent sur aucune de ces lignes et conservent leurs valeurs.

Pour aller plus loin

L’approche ci-dessous consiste à conserver deux booléens supplémentaires. Peux-tu te contenter d’un seul, en utilisant matrix[0][0] pour représenter la première ligne ?

Solution

Un 0 que tu écris ressemble exactement à un 0 déjà présent, donc effacer des lignes pendant le parcours propage les zéros dans toute la matrice. Sépare la lecture de l’écriture : enregistre d’abord les lignes et les colonnes qui contenaient un 0, puis efface-les. Conserve ces informations dans deux tableaux ou, pour utiliser un espace supplémentaire O(1), dans la première ligne et la première colonne de la matrice elle-même.

Marquer les lignes et les colonnes dans deux tableaux

Intuition

Une cellule devient 0 exactement lorsque sa ligne ou sa colonne contenait un 0 au départ. Enregistrez donc deux listes d’informations, zeroRow[i] et zeroCol[j], lors d’un parcours qui n’effectue aucune écriture, puis effacez chaque cellule dont la ligne ou la colonne est marquée. Rien ne se propage, car toutes les lectures sont effectuées avant la première écriture.

Chaque parcours visite les m·n cellules une seule fois, donc le temps d’exécution est O(m·n), et les tableaux contiennent m + n booléens.

Algorithme

Créez zeroRow avec m entrées et zeroCol avec n entrées, toutes à false.
Parcourez chaque cellule. Lorsque matrix[i][j] vaut 0, définissez zeroRow[i] et zeroCol[j] sur true.
Parcourez à nouveau chaque cellule et définissez-la sur 0 lorsque zeroRow[i] ou zeroCol[j] vaut true.
Retournez la matrice.

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 matrix

Utilisez la première ligne et la première colonne comme marqueurs

Intuition

La première colonne contient une cellule par ligne et la première ligne une cellule par colonne : elles ont la forme des deux tableaux de marqueurs. Ainsi, un 0 à la ligne i, colonne j écrit 0 dans matrix[i][0] et matrix[0][j]. Cela ne fait rien perdre : chacune de ces cellules se trouve sur une ligne ou une colonne qui doit de toute façon devenir 0.

La ligne 0 et la colonne 0 contiennent à la fois des données et des marqueurs, et un marqueur à ces endroits masque le fait qu’elles contenaient peut-être déjà un 0. Vérifie-les donc en premier et conserve les réponses dans deux booléens. Marque et remplis uniquement les cellules avec i ≥ 1 et j ≥ 1, puis efface la ligne 0 et la colonne 0 en dernier, car le remplissage les lit.

Dans le deuxième exemple, le 3 à la ligne 1, colonne 1 reste intact, car ses marqueurs, matrix[1][0] = 9 et matrix[0][1] = 4, ne sont pas égaux à 0. La complexité temporelle reste O(m·n), avec deux booléens de mémoire supplémentaire (O(m·n) en R, qui commence par copier l’entrée).

Algorithme

Définis firstRowZero si la ligne 0 contient un 0 et firstColZero si la colonne 0 contient un 0.
Pour chaque cellule contenant 0 avec i ≥ 1 et j ≥ 1, définis matrix[i][0] et matrix[0][j] à 0.
Pour chaque cellule avec i ≥ 1 et j ≥ 1, définis-la à 0 lorsque matrix[i][0] ou matrix[0][j] vaut 0.
Si firstRowZero est vrai, définis la ligne 0 à 0. Si firstColZero est vrai, définis la colonne 0 à 0.
Retourne la matrice.

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

Pièges et cas limites

Effacer une ligne et une colonne dès que vous trouvez un 0. Dans le premier exemple, le nouveau 0 à la ligne 1, colonne 2 efface ensuite la colonne 2, et seul le 3 en haut à gauche est conservé.
Laisser matrix[0][0] marquer à la fois la ligne 0 et la colonne 0. Dans [[1, 2, 3], [0, 5, 6], [7, 8, 9]], le 0 de la colonne 0 efface alors à tort la ligne 0.
Effacer la ligne 0 ou la colonne 0 avant le remplissage. Dans [[0, 2, 3], [4, 5, 6], [7, 8, 9]], toutes les colonnes semblent alors marquées, et toute la matrice devient 0.
Oublier les lignes uniques. Avec une seule ligne, les boucles qui commencent à 1 ne font rien et les booléens font tout le travail : [[1, 0, 3]] doit devenir [[0, 0, 0]].

Questions fréquentes3

Pourquoi ne peux-tu pas définir les zéros pendant que tu parcours la matrice ?

Un 0 que tu écris ressemble à un 0 d’origine. Quand le balayage l’atteint, il efface sa propre ligne et sa propre colonne, et ces nouveaux zéros se propagent davantage. Note chaque zéro d’origine avant de modifier une cellule.

Quelle est la complexité temporelle de Set Matrix Zeroes ?

O(m·n) pour une matrice m × n, puisque chaque cellule est lue et écrite un nombre constant de fois. Aucune solution ne fait mieux, car toute cellule ignorée pourrait être le 0 qui change la réponse. L’espace supplémentaire est de O(m + n) avec des tableaux marqueurs et de O(1) en utilisant la première ligne et la première colonne comme marqueurs.

Peux-tu marquer les cellules avec une valeur spéciale au lieu de 0 ?

Certaines solutions écrivent un marqueur dans les cellules à effacer, puis remplacent les marqueurs par des zéros à la fin. Cela ne fonctionne que si le marqueur ne peut jamais apparaître dans l’entrée, ce qu’une matrice d’entiers garantit rarement. L’écrire le long d’une ligne et d’une colonne pour chaque 0 coûte également O(m·n·(m + n)) en temps.

def setZeroes(matrix):
    # Écrivez le code ici

Test #1

Test #2

Argument

matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]

Résultat attendu

[[3, 0, 1], [0, 0, 0], [2, 0, 4]]