Rotate Image

Q: Bir matrisi döndürmenin zaman ve uzay karmaşıklığı nedir?

n × n matrisini döndürmek O(n²) zaman alır; çünkü neredeyse her değerin bir kez taşınması gerekir. Transpoze etme ve tersine çevirme yöntemi O(1) ek alan gerektirir. Döndürülmüş bir kopya oluşturmak da O(n²) zaman alır, ancak O(n²) ek alan kullanır.

OrtaDiziler ve dizgiler Matematik ve simülasyon

+10

Sana her satırı bir liste olan n × n boyutunda bir tamsayı ızgarası veriliyor. Izgarayı saat yönünde çeyrek tur döndür ve geri döndür. En üst satır en sağdaki sütun olur, ikinci satır onun solundaki sütun olur ve bu böyle devam eder: (i, j) konumundaki değer (j, n-1-i) konumuna gelir. Izgarayı yerinde değiştirebilirsin; onu geri döndür.

Fonksiyon

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

matrixinteger-2d-array: kare ızgara, her satır için bir iç liste
Döndürürinteger-2d-array: matris saat yönünde 90 derece döndü

Kısıtlar

n == matrix.length == matrix[i].length
1 ≤ n ≤ 70
-1000 ≤ matrix[i][j] ≤ 1000

Örnekler

Girdi: matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
Çıktı: [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
Açıklama: İlk satır olan 3 7 1, yukarıdan aşağıya okunduğunda son sütun olur. Aşağıdan yukarıya okunan ilk sütun olan 3 9 4, ilk satır [4, 9, 3] olur. Ortadaki 5 değeri yerinde kalır.

Ek soru

Bir matrisi 180 derece döndürmek için yerinde hangi iki adım uygulanır ve bunu tek bir takas geçişinde yapabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her değerin nereye gideceği bir formülle belirlenir: (i, j), (j, n-1-i) konumuna geçer. Zor olan, ikinci bir matris kullanmadan değerleri taşımaktır; çünkü bir değeri yeni hücresine yazmak, henüz taşınmamış bir değerin üzerine yazar. Önce transpoze edip ardından satırları ters çevirmek, aynı çeyrek dönüşü ikili takaslarla gerçekleştirir.

Döndürülmüş bir kopya oluştur

Sezgi

i satırı, n-1-i sütunu olur ve satırdaki j konumundaki değer, o sütunda j konumuna, yani j satırına gelir. Dolayısıyla result[j][n-1-i] = matrix[i][j]. İlk örnekte 2. satır, 0. sütundaki 4, 0. satır, 0. sütuna gider; bu yüzden cevap 4 ile başlar.

Değerler dörtlü döngüler boyunca hareket eder, bu nedenle doğrudan yerinde yazmak, bir değer hareket etmeden önce onun üzerine yazardı: 3, sağ üst köşedeki 1'in üzerine yazardı. Kopyalama işlemi n² ek hücreye mal olur; n = 70 için 4,900 hücre.

Algoritma

n × n boyutunda bir sonuç matrisi oluştur.
Her i satırı ve j sütunu için matrix[i][j] değerini result[j][n-1-i] içine kopyala.
Sonucu döndür.

def rotateImage(matrix):
    n = len(matrix)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # Row i becomes column n-1-i, read from top to bottom.
            result[j][n - 1 - i] = matrix[i][j]
    return result

Transpoze et, ardından her satırı tersine çevir

Sezgi

Transpozisyon (i, j) konumunu (j, i) konumuna taşır; bir satırı ters çevirmek ise c sütununu n-1-c sütununa taşır. Birlikte (i, j) konumunu (j, n-1-i) konumuna taşırlar; bu da döndürmenin onu yerleştirdiği konumdur.

Her iki işlem de yerinde çalışır, çünkü her biri bir çift takası dizisidir. Transpozisyonda matrix[i][j] ve matrix[j][i] hücrelerinin her biri diğerinin hücresine ait olduğundan, tek bir takas ikisini de tamamlar. Yalnızca j > i olan çiftleri takas et; yoksa her çift tekrar eski hâline döner. Bir satırı ters çevirmek, iki ucunu takas edip içe doğru ilerler.

İlk örnekte transpozisyon [[3, 9, 4], [7, 5, 8], [1, 2, 6]] sonucunu verir: her satır artık eski bir sütunu içerir. Her satırı ters çevirmek cevabı verir.

Transpozisyon n(n-1)/2 takas yapar; ters çevirmeler ise n·⌊n/2⌋ takas yapar. Bu nedenle işlem, birkaç ek bellek değişkeniyle O(n²) zaman alır. R sürümü önce girdiyi bir R matrisine kopyaladığından, ek bellek kullanımı O(n²) olur.

Algoritma

Ana köşegenin üzerindeki her hücre için, (i, j) ve j > i iken, değerini (j, i) hücresiyle değiştir.
Her satırda ilk ve son değerleri yer değiştir ve iki uç buluşana kadar içeri doğru ilerle.
Matrisi döndür.

def rotateImage(matrix):
    n = len(matrix)
    # Transpose: swap each value above the diagonal with its mirror below it.
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row with two pointers.
    for row in matrix:
        left, right = 0, n - 1
        while left < right:
            row[left], row[right] = row[right], row[left]
            left += 1
            right -= 1
    return matrix

Tuzaklar ve uç durumlar

j 0'dan başlarken transpoze etmek. Her çift iki kez yer değiştirir ve bu da transpozeyi iptal eder; böylece sonuç yalnızca satırların ters çevrilmiş hâli, yani ayna görüntüsü olur.
Transpoze etmeden önce ters çevirmek. Bu sıra matrisi saat yönünün tersine döndürür. 2 × 2'lik bir test bunu yakalar: [[1, 2], [3, 4]], [[3, 1], [4, 2]] hâline gelmelidir.
matrix[j][n-1-i] = matrix[i][j] ifadesini aynı matrise yazmak. Hedef hücrede hâlâ yer değiştirmemiş bir değer bulunur ve bu değer kaybolur.
n-1-i yerine n-i kullanmak. 0 tabanlı indekslerde son sütun n-1 olduğundan, i = 0 için n-i dizinin sonunu aşar.

Sıkça sorulan sorular3

Bir matrisi döndürmenin zaman ve uzay karmaşıklığı nedir?

n × n matrisini döndürmek O(n²) zaman alır; çünkü neredeyse her değerin bir kez taşınması gerekir. Transpoze etme ve tersine çevirme yöntemi O(1) ek alan gerektirir. Döndürülmüş bir kopya oluşturmak da O(n²) zaman alır, ancak O(n²) ek alan kullanır.

Bir matrisi saat yönünün tersine nasıl döndürürsünüz?

İki adımın sırasını değiştir: önce her satırı ters çevir, ardından transpoze et. Ayrıca önce transpoze edip sonra satırların sırasını tersine çevirebilirsin. Her iki durumda da (i, j) konumundaki değer (n-1-j, i) konumuna gelir.

Dört değeri bir seferde taşıyarak bir matrisi döndürebilir misin?

Evet. Merkez dışındaki her değer dört hücreden oluşan bir döngüye aittir: (i, j), (j, n-1-i), (n-1-i, n-1-j) ve (n-1-j, i). Halkaları sırayla ele alarak, her döngünün bir değerini bir değişkende tutun ve diğer üçünü kaydırın. Zaman karmaşıklığı yine O(n²), alan karmaşıklığı O(1)'dir; ancak yanlış yapma ihtimali olan daha fazla indeks hesabı gerekir.

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

Test #1

Test #2

Argüman

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

Beklenen Çıktı

[[4, 9, 3], [8, 5, 7], [6, 2, 1]]