Set Matrix Zeroes

Q: Set Matrix Zeroes algoritmasının zaman karmaşıklığı nedir?

Bir m × n matrisi için O(m·n), çünkü her hücre sabit sayıda okunup yazılır. Hiçbir çözüm daha iyisini yapamaz; çünkü atlanan herhangi bir hücre, yanıtı değiştiren 0 olabilir. İşaretleyici diziler kullanıldığında ek alan O(m + n), ilk satır ve sütun işaretleyici olarak kullanıldığında ise O(1)’dir.

OrtaDiziler ve dizgiler Hashing

+10

Girdi, satır satır verilen m × n boyutunda bir tam sayı ızgarasıdır; dolayısıyla matrix[i][j], i. satırda ve j. sütunda bulunur. Izgarada 0 bulunan her yerde, o satırın ve o sütunun tamamını 0 yapın. Yalnızca başlangıçta mevcut olan sıfırlar dikkate alınır: 0'a dönüştürdüğünüz bir hücre, kendi satırını veya sütununu temizlemez. Izgarayı yerinde değiştirebilirsiniz; ızgarayı döndürün.

Fonksiyon

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

matrixinteger-2d-array: satır başına bir iç liste olacak şekilde tamsayılar ızgarası
Döndürürinteger-2d-array: İçinde 0 bulunan her satırın ve sütunun 0 olarak ayarlandığı matris

Kısıtlar

m == matrix.length ve n == matrix[i].length
1 ≤ m, n ≤ 1000 ve m × n ≤ 5000
All m satır n değer tutar.
-1000 ≤ matrix[i][j] ≤ 1000

Örnekler

Girdi: matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
Çıktı: [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
Açıklama: Tek 0, 1. satırın 1. sütununda yer alıyor. 1. satırın tamamı sıfır oluyor; 1. sütun da aynı şekilde, böylece 8 ve 6 da 0 oluyor. Dört köşe de bu iki çizginin hiçbirinde yer almıyor ve değerlerini koruyor.

Ek soru

Aşağıdaki en iyi yaklaşımda iki ek boole değeri kullanılıyor. matrix[0][0] ilk satırı temsil edecek şekilde tek bir boole değeriyle yetinebilir misin?

Çözüm

Yazdığın bir 0, sana verilen bir 0 ile tamamen aynı görünür; bu yüzden tarama sırasında satırları temizlemek, sıfırların matrise yayılmasına neden olur. Okumayı yazmadan ayır: önce hangi satır ve sütunlarda 0 bulunduğunu kaydet, ardından onları temizle. Bu kaydı iki dizide tut ya da O(1) ek alan kullanmak için matrisin kendi ilk satırını ve sütununu kullan.

İki dizide satırları ve sütunları işaretleyin

Sezgi

Bir hücre, yalnızca satırında veya sütununda başlangıçta 0 varsa 0 olur. Bu yüzden, hiçbir yere yazmadan yapılan bir geçişte zeroRow[i] ve zeroCol[j] olmak üzere iki olgu listesi kaydedin; ardından satırı veya sütunu işaretlenmiş olan her hücreyi temizleyin. Hiçbir şey yayılmaz, çünkü tüm okumalar ilk yazma işleminden önce yapılır.

Her geçiş m·n hücreyi bir kez ziyaret eder; bu nedenle zaman karmaşıklığı O(m·n) olur ve diziler m + n boole değeri tutar.

Algoritma

m elemanlı zeroRow ve n elemanlı zeroCol oluştur; tüm elemanları false olsun.
Her hücreyi tara. matrix[i][j] 0 olduğunda, zeroRow[i] ve zeroCol[j] değerlerini true olarak ayarla.
Her hücreyi tekrar tara ve zeroRow[i] veya zeroCol[j] true olduğunda hücreyi 0 olarak ayarla.
Matrisi döndür.

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

İşaretleyici olarak ilk satırı ve sütunu kullanın

Sezgi

İlk sütunda satır başına bir hücre, ilk satırda ise sütun başına bir hücre bulunur; bunlar iki işaretçi dizisinin boyutlarıdır. Bu nedenle i satırında, j sütunundaki bir 0, matrix[i][0] ve matrix[0][j] hücrelerine 0 yazar. Bu hiçbir bilgi kaybına yol açmaz: Bu hücrelerin her biri zaten 0 olması gereken bir satırda ya da sütunda bulunur.

0. satır ve 0. sütun hem veri hem de işaretçi olarak kullanılır; bu nedenle buraya konan bir işaret, hücrelerin başlangıçta kendilerinin 0 olup olmadığını gizler. Bu yüzden önce bunları kontrol edin ve sonuçları iki boole değişkeninde saklayın. Yalnızca i ≥ 1 ve j ≥ 1 olan hücreleri işaretleyip doldurun; doldurma işlemi bu satır ve sütunu okuduğu için 0. satır ve 0. sütunu en son temizleyin.

İkinci örnekte, 1. satırın 1. sütunundaki 3 korunur; çünkü işaretçileri olan matrix[1][0] = 9 ve matrix[0][1] = 4 0 değildir. Zaman karmaşıklığı, ek bellek olarak iki boole değişkeni kullanıldığında O(m·n) olarak kalır (girdiyi önce kopyaladığı için R'de O(m·n)).

Algoritma

Satır 0'da 0 varsa firstRowZero, sütun 0'da 0 varsa firstColZero değerini ayarla.
i ≥ 1 ve j ≥ 1 olan ve 0 içeren her hücre için matrix[i][0] ve matrix[0][j] değerlerini 0 olarak ayarla.
i ≥ 1 ve j ≥ 1 olan her hücreyi, matrix[i][0] veya matrix[0][j] 0 ise 0 olarak ayarla.
firstRowZero doğruysa satır 0'ı 0 olarak ayarla. firstColZero doğruysa sütun 0'ı 0 olarak ayarla.
Matrisi döndür.

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

Tuzaklar ve uç durumlar

Bir 0 bulur bulmaz bir satırı ve bir sütunu temizlemek. İlk örnekte, satır 1 sütun 2'deki yeni 0 ardından sütun 2'yi temizler ve yalnızca sol üstteki 3 kalır.
matrix[0][0] değerinin hem 0. satırı hem de 0. sütunu işaretlemesine izin vermek. [[1, 2, 3], [0, 5, 6], [7, 8, 9]] içinde, 0. sütundaki 0 yanlışlıkla 0. satırı da temizler.
Doldurma işleminden önce 0. satırı veya 0. sütunu temizlemek. [[0, 2, 3], [4, 5, 6], [7, 8, 9]] içinde her sütun işaretlenmiş gibi görünür ve tüm matris 0 olur.
Tek satırları veya sütunları unutmak. Tek satır olduğunda, 1'den başlayan döngüler hiçbir şey yapmaz ve tüm işi boole değerleri üstlenir: [[1, 0, 3]] değeri [[0, 0, 0]] olmalıdır.

Sıkça sorulan sorular3

Matris üzerinde tarama yaparken neden sıfırları ayarlayamıyorsun?

Yazdığın 0, başlangıçta var olan bir 0 ile aynı görünür. Tarama ona ulaştığında, bulunduğu satırı ve sütunu temizler; oluşan yeni sıfırlar da daha ileriye yayılır. Herhangi bir hücreyi değiştirmeden önce başlangıçta var olan tüm sıfırları kaydet.

Set Matrix Zeroes algoritmasının zaman karmaşıklığı nedir?

Bir m × n matrisi için O(m·n), çünkü her hücre sabit sayıda okunup yazılır. Hiçbir çözüm daha iyisini yapamaz; çünkü atlanan herhangi bir hücre, yanıtı değiştiren 0 olabilir. İşaretleyici diziler kullanıldığında ek alan O(m + n), ilk satır ve sütun işaretleyici olarak kullanıldığında ise O(1)’dir.

Hücreleri 0 yerine özel bir değerle işaretleyebilir misin?

Bazı çözümler, temizlenecek hücrelere bir yer tutucu yazar ve en sonunda yer tutucuları sıfırlara dönüştürür. Bu yalnızca yer tutucunun girdide asla bulunamayacağı garanti ediliyorsa işe yarar; tamsayı matrislerinde bu nadiren garanti edilir. Her 0 için bir satır ve sütun boyunca yer tutucu yazmak ayrıca O(m·n·(m + n)) zaman alır.

def setZeroes(matrix):
    # Kodu buraya yazın

Test #1

Test #2

Argüman

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

Beklenen Çıktı

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