Set Matrix Zeroes

Q: Apa kompleksitas waktu untuk Set Matrix Zeroes?

O(m·n) untuk matriks m × n , karena setiap sel dibaca dan ditulis beberapa kali dalam jumlah konstan. Tidak ada solusi yang lebih baik, karena sel yang dilewati bisa saja bernilai 0 dan mengubah jawabannya. Ruang tambahan adalah O(m + n) dengan array penanda dan O(1) dengan menggunakan baris dan kolom pertama sebagai penanda.

SedangArray dan string Hashing

+10

Input berupa grid bilangan bulat m × n, yang diberikan baris demi baris, sehingga matrix[i][j] berada di baris i dan kolom j. Di mana pun grid berisi 0, ubah seluruh baris dan seluruh kolom tersebut menjadi 0. Hanya nol yang sudah ada sejak awal yang dihitung: sel yang kamu ubah menjadi 0 tidak mengubah baris atau kolomnya sendiri. Kamu boleh mengubah grid secara langsung, lalu mengembalikannya.

Fungsi

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

matrixinteger-2d-array: grid yang terdiri dari bilangan bulat, satu list bagian dalam untuk setiap baris
Mengembalikaninteger-2d-array: matriks dengan setiap baris dan kolom yang memiliki 0 diubah menjadi 0

Batasan

m == matrix.length dan n == matrix[i].length
1 ≤ m, n ≤ 1000 dan m × n ≤ 5000
Semua m baris berisi n nilai.
-1000 ≤ matrix[i][j] ≤ 1000

Contoh

Input: matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
Output: [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
Penjelasan: Satu-satunya 0 berada di baris 1, kolom 1. Baris 1 menjadi semuanya 0, begitu juga kolom 1, yang mengubah 8 dan 6 menjadi 0. Keempat sudut tidak berada di kedua garis tersebut dan nilainya tetap.

Pertanyaan lanjutan

Pendekatan terbaik di bawah ini menyimpan dua nilai boolean tambahan. Bisakah kamu cukup menggunakan satu, dengan menjadikan matrix[0][0] sebagai penanda untuk baris pertama?

Solusi

Angka 0 yang kamu tulis terlihat persis seperti angka 0 yang sudah ada, jadi mengosongkan baris selama pemindaian menyebarkan angka nol ke seluruh matriks. Pisahkan pembacaan dan penulisan: catat terlebih dahulu baris dan kolom mana yang berisi angka 0, lalu kosongkan baris dan kolom tersebut. Simpan catatan itu dalam dua array, atau, untuk menggunakan ruang ekstra O(1), di baris dan kolom pertama matriks itu sendiri.

Tandai baris dan kolom dalam dua array

Intuisi

Sebuah sel menjadi 0 tepat ketika baris atau kolomnya memiliki 0 sejak awal. Jadi, catat dua daftar fakta, zeroRow[i] dan zeroCol[j], dalam satu iterasi yang tidak pernah menulis, lalu kosongkan setiap sel yang baris atau kolomnya ditandai. Tidak ada nilai yang menyebar, karena semua pembacaan dilakukan sebelum penulisan pertama.

Setiap iterasi mengunjungi m·n sel satu kali, jadi waktunya adalah O(m·n), dan array menampung m + n nilai boolean.

Algoritma

Buat zeroRow dengan m entri dan zeroCol dengan n entri, semuanya bernilai false.
Periksa setiap sel. Jika matrix[i][j] bernilai 0, atur zeroRow[i] dan zeroCol[j] menjadi true.
Periksa kembali setiap sel dan atur nilainya menjadi 0 jika zeroRow[i] atau zeroCol[j] bernilai true.
Kembalikan matrix.

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

Gunakan baris dan kolom pertama sebagai penanda

Intuisi

Kolom pertama memiliki satu sel untuk setiap baris, dan baris pertama memiliki satu sel untuk setiap kolom, sesuai bentuk kedua array penanda. Jadi, nilai 0 pada baris i, kolom j menulis 0 ke matrix[i][0] dan matrix[0][j]. Tidak ada informasi yang hilang: masing-masing sel tersebut berada pada garis yang memang harus menjadi 0.

Baris 0 dan kolom 0 berisi data sekaligus penanda, dan sebuah penanda di sana menyamarkan apakah sel tersebut sebelumnya berisi 0. Jadi, periksa keduanya terlebih dahulu dan simpan jawabannya dalam dua nilai boolean. Tandai dan isi hanya sel dengan i ≥ 1 dan j ≥ 1, lalu kosongkan baris 0 dan kolom 0 terakhir, karena proses pengisian membaca keduanya.

Pada contoh kedua, angka 3 di baris 1, kolom 1 tetap ada karena penandanya, matrix[1][0] = 9 dan matrix[0][1] = 4, bukan 0. Waktu eksekusi tetap O(m·n), dengan dua nilai boolean sebagai memori tambahan (O(m·n) di R, yang terlebih dahulu menyalin input).

Algoritma

Tetapkan firstRowZero jika baris 0 berisi 0 dan firstColZero jika kolom 0 berisi 0.
Untuk setiap sel dengan i ≥ 1 dan j ≥ 1 yang berisi 0, tetapkan matrix[i][0] dan matrix[0][j] menjadi 0.
Untuk setiap sel dengan i ≥ 1 dan j ≥ 1, tetapkan nilainya menjadi 0 jika matrix[i][0] atau matrix[0][j] bernilai 0.
Jika firstRowZero bernilai benar, tetapkan baris 0 menjadi 0. Jika firstColZero bernilai benar, tetapkan kolom 0 menjadi 0.
Kembalikan matrix.

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

Jebakan dan kasus tepi

Mengosongkan baris dan kolom segera setelah kamu menemukan 0. Pada contoh pertama, 0 baru di baris 1, kolom 2 lalu mengosongkan kolom 2, dan hanya angka 3 di kiri atas yang tersisa.
Membiarkan matrix[0][0] menandai baris 0 sekaligus kolom 0. Dalam [[1, 2, 3], [0, 5, 6], [7, 8, 9]], 0 di kolom 0 lalu keliru mengosongkan baris 0.
Mengosongkan baris 0 atau kolom 0 sebelum pengisian. Dalam [[0, 2, 3], [4, 5, 6], [7, 8, 9]], setiap kolom lalu tampak sudah ditandai, dan seluruh matrix menjadi 0.
Melupakan baris tunggal. Jika hanya ada satu baris, perulangan yang dimulai dari 1 tidak melakukan apa pun, dan semua pekerjaan dilakukan oleh nilai boolean: [[1, 0, 3]] harus menjadi [[0, 0, 0]].

Pertanyaan yang sering diajukan3

Mengapa kamu tidak bisa menetapkan nilai nol saat memindai matriks?

Angka 0 yang kamu tulis terlihat sama seperti angka 0 asli. Saat pemindaian mencapainya, angka itu mengubah baris dan kolomnya sendiri menjadi 0, lalu angka-angka 0 baru itu menyebar lebih jauh. Catat setiap angka 0 asli sebelum kamu mengubah sel mana pun.

Apa kompleksitas waktu untuk Set Matrix Zeroes?

O(m·n) untuk matriks m × n, karena setiap sel dibaca dan ditulis beberapa kali dalam jumlah konstan. Tidak ada solusi yang lebih baik, karena sel yang dilewati bisa saja bernilai 0 dan mengubah jawabannya. Ruang tambahan adalah O(m + n) dengan array penanda dan O(1) dengan menggunakan baris dan kolom pertama sebagai penanda.

Bisakah kamu menandai sel dengan nilai khusus alih-alih 0?

Beberapa solusi menulis nilai sementara ke dalam sel yang perlu dikosongkan, lalu mengubah nilai sementara menjadi nol di akhir. Cara ini hanya berhasil jika nilai sementara tidak mungkin muncul dalam input, yang jarang dapat dijamin oleh matriks bilangan bulat. Menuliskannya di sepanjang baris dan kolom untuk setiap 0 juga membutuhkan waktu O(m·n·(m + n)).

def setZeroes(matrix):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

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

Output yang diharapkan

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