Transpose Matrix

Q: Bir matrisi transpoze etmenin zaman karmaşıklığı nedir?

O(m × n) : m × n değerlerinin her biri bir kez kopyalanır ve bundan daha azı sonucu üretemez. Yeni matris, çıktının kendi boyutu olan O(m × n) alan kaplar.

BaşlangıçDiziler ve dizgiler

+10

Bir satır listesi olarak bir tamsayı matrisi alırsın: matrix[i][j], i. satırdaki j. sütunun değeridir. Transpozunu döndür: i. satırdaki j. sütunun değeri j. satırdaki i. sütuna taşınır; böylece her satır bir sütun olur. Matrisin kare olması gerekmez: m × n boyutundaki bir matris, n × m boyutunda bir matrise dönüşür.

Fonksiyon

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

matrixinteger-2d-array: m × n matrisi, her biri n tam sayıdan oluşan m satırlık bir liste olarak
Döndürürinteger-2d-array: n satır ve her satırda m tam sayı bulunan n × m transpozu

Kısıtlar

1 ≤ m, n ≤ 1000; burada m = matrix.length ve n = matrix[i].length
m × n ≤ 5000
Her satırın uzunluğu n ile aynıdır.
-1000 ≤ matrix[i][j] ≤ 1000

Örnekler

Girdi: matrix = [[1, 2, 3], [4, 5, 6]]
Çıktı: [[1, 4], [2, 5], [3, 6]]
Açıklama: [1, 2, 3] satırı ilk sütun, [4, 5, 6] ise ikinci sütun olur. Satır satır okunduğunda sonuç [1, 4], [2, 5], [3, 6] şeklindedir: 3 × 2'lik bir matris.

Ek soru

Matrisin, satır satır sıralanmış m × n değerden oluşan tek bir düz dizide saklandığını varsayalım. İkinci bir dizi kullanmadan, kare olmayan bir matrisi bu dizinin içinde transpoze edebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Transpozisyon hiçbir hesaplama yapmaz: (i, j) konumundaki değer (j, i) konumuna taşınır. İşin özü şekildir. Sonuç, uzunluğu m olan n satır içerir; bu nedenle kare olmayan bir satır listesi yerinde transpoze edilemez. Tersine çevrilmiş boyutlarda yeni bir matris oluşturup içini doldurun.

Matris'i her seferinde bir sütun okuyun

Sezgi

Yanıtın j. satırı, yukarıdan aşağıya okunan girdinin j. sütunudur. [[1, 2, 3], [4, 5, 6]] için 0. sütun önce 1'i, sonra 4'ü verir; bu nedenle yanıtın ilk satırı [1, 4] olur.

Her değer bir kez okunur ve bir kez yazılır: O(m × n) zaman ve sonuç için O(m × n) alan gerekir. Her yeni satırı oluşturmak, bir girdi satırı boyunca ilerlemek yerine tüm girdi satırlarının üzerinden atlamayı gerektirir; bellekte ilerlemenin daha yavaş yolu budur.

Algoritma

m satır sayısı, n ise bir satırın uzunluğu olsun.
0'dan n-1'e kadar her j sütunu için boş bir liste başlat.
0'dan m-1'e kadar her i için matrix[i][j]'yi bu listeye ekle.
Listeyi j. satır olarak sonuca ekle ve son sütundan sonra sonucu döndür.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    result = []
    for j in range(n):
        # Column j, read top to bottom, becomes row j of the answer.
        column = []
        for i in range(m):
            column.append(matrix[i][j])
        result.append(column)
    return result

Her hücreyi yansıtarak yeni bir n × m ızgarayı doldurun

Sezgi

n × m boyutundaki sonucu en başta oluştur, ardından girdiyi depolandığı sırayla, satır satır oku ve her değeri ayna konumuna yerleştir: result[j][i] = matrix[i][j]. Bu doğrudur çünkü transpoz, bu indekslerin her hücreye bir kez uygulanan tam olarak bu şekilde yer değiştirmesidir.

Her değer bir kez kopyalandığından, zaman karmaşıklığı O(m × n) olur ve ızgara, çıktının zaten ihtiyaç duyduğu O(m × n) alanı kaplar. Satırlar boyunca okumak belleği depolanma sırasıyla ziyaret eder ve sonuçtaki her satır, son boyutunda bir kez ayrılır.

Algoritma

m, satır sayısı ve n, bir satırın uzunluğu olsun.
Her biri m değer içeren n satırlı bir result oluşturun.
Girdinin her i satırı ve her j sütunu için result[j][i] = matrix[i][j] olarak ayarlayın.
result değerini döndürün.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    # The answer has n rows of m values each.
    result = [[0] * m for _ in range(n)]
    for i in range(m):
        for j in range(n):
            result[j][i] = matrix[i][j]
    return result

Tuzaklar ve uç durumlar

Sonucu girdinin şekliyle oluşturmak. 2 × 3 örneğinde result[2][0] yazmak dizinin sonunu aşar: sonucun, her biri m uzunluğunda n satıra ihtiyacı vardır.
matrix[i][j] ile matrix[j][i] değerlerini yerinde değiştirmek. Bu yalnızca m = n olduğunda ve yalnızca j > i olan hücrelerde işe yarar; her hücre üzerinde döngü kurmak her çifti iki kez değiştirir ve matrisi değişmeden bırakır.
Python'da [[0] * m] * n, tek bir listeye n başvuru oluşturur; bu nedenle bir hücreye yazmak bütün bir sütunu yazar. Her satırı ayrı ayrı oluştur.
C'de çağıran taraf, *returnSize değerini sonuç satırlarının sayısı, n, ve (*returnColumnSizes)[j] değerini her satırın uzunluğu, m, olarak okur.

Sıkça sorulan sorular3

Bir matrisin transpozu nedir?

Satırları ve sütunları yer değiştirerek elde ettiğin matristir: i. satır, j. sütundaki değer, j. satır, i. sütuna taşınır. 2 × 3 boyutundaki bir matris 3 × 2 boyutuna dönüşür ve iki kez transpozunu almak matrisi eski hâline getirir.

Bir matrisi transpoze etmenin zaman karmaşıklığı nedir?

O(m × n): m × n değerlerinin her biri bir kez kopyalanır ve bundan daha azı sonucu üretemez. Yeni matris, çıktının kendi boyutu olan O(m × n) alan kaplar.

Bir matrisi yerinde transpoze edebilir misin?

Kare bir matris için evet: köşegenin üzerindeki her hücre için matrix[i][j] ile matrix[j][i] değerlerini, ek O(1) bellek kullanarak yer değiştirin. Kare olmayan bir matrisin şekli değişir; bu nedenle satır listesi kullanıyorsanız yeni bir matrise ihtiyacınız vardır.

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

Test #1

Test #2

Argüman

matrix = [[1, 2, 3], [4, 5, 6]]

Beklenen Çıktı

[[1, 4], [2, 5], [3, 6]]