Set Matrix Zeroes

Q: Qual è la complessità temporale di Set Matrix Zeroes?

O(m·n) per una matrice m × n , poiché ogni cella viene letta e scritta un numero costante di volte. Nessuna soluzione è più efficiente, perché qualsiasi cella saltata potrebbe essere lo 0 che cambia la risposta. Lo spazio aggiuntivo è O(m + n) con array di marcatori e O(1) usando la prima riga e la prima colonna come marcatori.

MedioArray e stringhe Hashing

+10

L’input è una griglia m × n di interi, fornita riga per riga, quindi matrix[i][j] si trova nella riga i e nella colonna j. Ovunque la griglia contenga uno 0, imposta a 0 l’intera riga e l’intera colonna corrispondenti. Conta solo gli zeri presenti all’inizio: una cella che trasformi in 0 non azzera la propria riga o colonna. Puoi modificare la griglia sul posto; restituiscila.

Funzione

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

matrixinteger-2d-array: la griglia di numeri interi, una lista interna per riga
Restituisceinteger-2d-array: la matrice con ogni riga e ogni colonna che contenevano uno 0 impostate a 0

Vincoli

m == matrix.length e n == matrix[i].length
1 ≤ m, n ≤ 1000 and m × n ≤ 5000
Tutte le righe m contengono n valori.
-1000 ≤ matrix[i][j] ≤ 1000

Esempi

Input: matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
Output: [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
Spiegazione: L’unico 0 si trova nella riga 1, colonna 1. La riga 1 diventa composta solo da zeri, e lo stesso vale per la colonna 1, che trasforma l’8 e il 6 in 0. I quattro angoli non si trovano in nessuna delle due linee e mantengono i loro valori.

Per approfondire

L'approccio migliore qui sotto mantiene due booleani aggiuntivi. Riesci a cavartela con uno solo, facendo sì che matrix[0][0] rappresenti la prima riga?

Soluzione

Uno 0 che scrivi è identico a uno 0 che ti è stato dato, quindi azzerare le righe durante la scansione diffonde gli zeri nella matrice. Separa la lettura dalla scrittura: prima registra quali righe e colonne contenevano uno 0, poi azzerale. Conserva queste informazioni in due array oppure, per usare uno spazio aggiuntivo O(1), nella prima riga e nella prima colonna della matrice stessa.

Contrassegna righe e colonne in due array

Intuizione

Una cella diventa 0 esattamente quando la sua riga o la sua colonna conteneva uno 0 all'inizio. Quindi registra due elenchi di informazioni, zeroRow[i] e zeroCol[j], in un passaggio che non scrive, poi azzera ogni cella la cui riga o colonna è contrassegnata. Nulla si propaga, perché tutte le letture avvengono prima della prima scrittura.

Ogni passaggio visita una volta le m·n celle, quindi il tempo è O(m·n) e gli array contengono m + n valori booleani.

Algoritmo

Crea zeroRow con m elementi e zeroCol con n elementi, tutti false.
Esamina ogni cella. Quando matrix[i][j] è 0, imposta zeroRow[i] e zeroCol[j] su true.
Esamina di nuovo ogni cella e impostala a 0 quando zeroRow[i] o zeroCol[j] è true.
Restituisci 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

Usa la prima riga e la prima colonna come indicatori

Intuizione

La prima colonna ha una cella per riga e la prima riga una cella per colonna: queste sono le forme dei due array marcatori. Quindi uno 0 alla riga i, colonna j scrive 0 in matrix[i][0] e matrix[0][j]. Non si perde nulla: ciascuna di queste celle si trova su una riga o colonna che deve comunque diventare 0.

La riga 0 e la colonna 0 sono sia dati sia marcatori, e un marcatore in quella posizione nasconde se contenevano uno 0 proprio. Quindi controllale per prime e conserva le risposte in due valori booleani. Marca e riempi solo le celle con i ≥ 1 e j ≥ 1, e azzera la riga 0 e la colonna 0 per ultime, perché il riempimento le legge.

Nel secondo esempio il 3 alla riga 1, colonna 1 resta invariato perché i suoi marcatori, matrix[1][0] = 9 e matrix[0][1] = 4, non sono 0. La complessità temporale resta O(m·n) con due valori booleani di memoria aggiuntiva (O(m·n) in R, che prima copia l’input).

Algoritmo

Imposta firstRowZero se la riga 0 contiene uno 0 e firstColZero se la colonna 0 contiene uno 0.
Per ogni cella con i ≥ 1 e j ≥ 1 che contiene 0, imposta matrix[i][0] e matrix[0][j] a 0.
Per ogni cella con i ≥ 1 e j ≥ 1, impostala a 0 quando matrix[i][0] o matrix[0][j] è 0.
Se firstRowZero è vero, imposta la riga 0 a 0. Se firstColZero è vero, imposta la colonna 0 a 0.
Restituisci 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

Trappole e casi limite

Cancellare una riga e una colonna non appena trovi uno 0. Nel primo esempio, il nuovo 0 alla riga 1, colonna 2 cancella poi la colonna 2, e sopravvive solo il 3 in alto a sinistra.
Lasciare che matrix[0][0] contrassegni sia la riga 0 sia la colonna 0. In [[1, 2, 3], [0, 5, 6], [7, 8, 9]] lo 0 nella colonna 0 cancella quindi erroneamente la riga 0.
Cancellare la riga 0 o la colonna 0 prima del riempimento. In [[0, 2, 3], [4, 5, 6], [7, 8, 9]] tutte le colonne risultano quindi contrassegnate e l'intera matrice diventa 0.
Dimenticare le righe singole. Con una sola riga, i cicli che iniziano da 1 non fanno nulla e i valori booleani fanno tutto il lavoro: [[1, 0, 3]] deve diventare [[0, 0, 0]].

Domande frequenti3

Perché non puoi impostare gli zeri mentre scansioni la matrice?

Uno 0 che scrivi ha lo stesso aspetto di uno 0 originale. Quando la scansione lo raggiunge, azzera la propria riga e colonna, e questi nuovi zeri si propagano ulteriormente. Registra ogni zero originale prima di modificare qualsiasi cella.

Qual è la complessità temporale di Set Matrix Zeroes?

O(m·n) per una matrice m × n, poiché ogni cella viene letta e scritta un numero costante di volte. Nessuna soluzione è più efficiente, perché qualsiasi cella saltata potrebbe essere lo 0 che cambia la risposta. Lo spazio aggiuntivo è O(m + n) con array di marcatori e O(1) usando la prima riga e la prima colonna come marcatori.

Puoi contrassegnare le celle con un valore speciale invece di 0?

Alcune soluzioni inseriscono un segnaposto nelle celle da azzerare e alla fine trasformano i segnaposto in zeri. Funziona solo se il segnaposto non può mai comparire nell’input, cosa che una matrice di interi raramente garantisce. Inserirlo lungo una riga e una colonna per ogni 0 richiede inoltre un tempo pari a O(m·n·(m + n)).

def setZeroes(matrix):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

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

Output atteso

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