Transpose Matrix

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

Bu O(m × n) olur, çünkü m × n değerlerin her biri bir kez kopyalanır ve bundan daha azı yanıtı oluşturamaz. Yeni matris, çıktının kendi boyutu olan O(m × n) alan kaplar.

Q: Bir matrisi yerinde transpoze edebilir misin?

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

Q: Kare olmayan bir matrisi nasıl transpoze edersiniz?

Girdinin n satır ve m uzunluğunda satırlardan oluştuğu durumda, m satır ve n uzunluğunda satırlardan oluşan bir sonuç oluştur. Ardından her değeri result[j][i] = matrix[i][j] ile kopyala. Kare matris durumundaki köşegen fikri burada geçerli değildir, çünkü iki matrisin şekli aynı değildir.

BaşlangıçDiziler ve dizgiler

+10

Satır listesi olarak bir tamsayı matrisi alırsın: matrix[i][j], i satırında, j sütunundaki değerdir. Transpozunu, yani her satırı bir sütuna dönüştürerek elde ettiğin matrisi döndür. i satırındaki, j sütunundaki değer j satırına, i sütununa taşınır. 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 satır ve her satırda n tam sayıdan oluşan m × n matrisi
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 aynıdır: n.
-1000 ≤ matrix[i][j] ≤ 1000

Örnekler

Girdi: matrix = [[1, 2, 3], [4, 5, 6]]
Çıktı: [[1, 4], [2, 5], [3, 6]]
Açıklama: İlk satır [1, 2, 3] ilk sütun, [4, 5, 6] ise ikinci sütun olur. Sonucu satır satır okuduğumuzda [1, 4], [2, 5], [3, 6] elde ederiz: 2 × 3'lük matris, 3 × 2'lik bir matrise dönüşür.

Gönderirken +15 gizli test

Ek soru

Matrisin, satır satır, m × n değer içeren tek bir düz dizide saklandığını varsayalım. Kare olmayan bir matrisi ikinci bir dizi kullanmadan 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

Transpoze etme, adresin saf bir değişikliğidir: (i, j) konumundaki değer (j, i) konumuna taşınır ve hiçbir hesaplama yapılmaz. Yapılması gereken, şekli doğru ayarlamaktır. Satır listesi olarak saklanan kare olmayan bir matris yerinde transpoze edilemez; çünkü sonuçta m uzunluğunda n satır yerine n uzunluğunda m satır bulunur. Bu yüzden boyutları yer değiştirilmiş yeni bir matris oluşturup doldurursun.

Matrisi her seferinde bir sütun okuyun

Sezgi

Yanıtın j satırı, girdinin yukarıdan aşağıya okunan j sütunudur. Bu yüzden yanıtı her seferinde bir satır oluşturarak kurun: 0 ile n-1 arasındaki her j sütunu için matrix[0][j], matrix[1][j] ve matrix[m-1][j] değerine kadar devamını toplayın ve bu listeyi sonraki satır olarak ekleyin.

[[1, 2, 3], [4, 5, 6]] için 0. sütun 1 sonra 4, 1. sütun 2 sonra 5, 2. sütun 3 sonra 6 olarak okunur. Yanıt, m = 2 değerinden oluşan n = 3 satırlı [[1, 4], [2, 5], [3, 6]] olur.

Her değer bir kez okunup bir kez yazılır; bu nedenle zaman karmaşıklığı O(m × n), sonucun kapladığı alan ise O(m × n) olur. Maliyet erişim düzeninden kaynaklanır: yeni bir satır oluştururken girdi matrisinin her satırına dokunulur ve bir satır boyunca okumak yerine satırdan satıra atlanır.

Algoritma

m satır sayısı, n ise bir satırın uzunluğu olsun.
0 ile n-1 arasındaki her j sütunu için boş bir liste başlatın.
0 ile m-1 arasındaki her i için matrix[i][j] değerini bu listeye ekleyin.
Listeyi j. satır olarak sonuca ekleyin ve son sütundan sonra sonucu döndürün.

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 aynalayarak yeni bir n × m ızgarayı doldurun

Sezgi

Önce şekle karar ver, sonra doldur. Yanıtın uzunluğu m olan n satırı var; bu yüzden ızgarayı en baştan oluştur. Ardından girdiyi doğal sırasıyla, satır satır ve soldan sağa oku ve her değeri aynalanmış konumuna yerleştir: result[j][i] = matrix[i][j].

Kural doğrudur, çünkü transpoze etmek tam olarak iki indeksi yer değiştirmektir. Kare örnekte [[1, 2], [3, 4]], köşegendeki 1 ve 4 yerlerinde kalır, 2 (0, 1) konumundan (1, 0) konumuna, 3 ise (1, 0) konumundan (0, 1) konumuna gider ve sonuç [[1, 3], [2, 4]] olur.

m × n değerin her biri bir kez kopyalanır; bu nedenle zaman karmaşıklığı O(m × n) olur ve yeni ızgara, çıktının zaten gerektirdiği O(m × n) alanı kullanır. Girdiyi satırları boyunca okumak, belleği depolandığı sırayla ziyaret eder ve her sonuç satırı son boyutunda bir kez oluşturulur.

Algoritma

m, satır sayısı; n ise bir satırın uzunluğu olsun.
n satırdan oluşan ve her satırında m değer bulunan result'ı oluştur.
Girdinin her i satırı ve her j sütunu için result[j][i] = matrix[i][j] değerini ata.
result'ı döndür.

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

Yanlış yanıtların neredeyse tamamı değerlerden değil, şekilden kaynaklanır.

Sonucu özgün şekliyle oluşturmak. m satır ve n sütundan oluşan bir sonuç yalnızca kare girdi için çalışır; 2 × 3 örneğinde result[2][0] yazmak sınırların dışına çıkar. Sonuç, uzunluğu m olan n satıra sahip olmalıdır.
Kare olmayan bir matriste yerinde takas yapmak. matrix[i][j] ile matrix[j][i] değerlerini takas etmek yalnızca m = n olduğunda çalışır; bu durumda bile döngü yalnızca köşegenin üstündeki hücreleri (j > i) kapsamalıdır, yoksa her çift iki kez takas edilir ve matris başlangıç hâline döner.
Aynı satır nesnesini paylaşmak. Python'da [[0] * m] * n, aynı listeye n referans oluşturur; bu nedenle bir hücreye yazmak sütunun tamamını yazar. Her satırı ayrı ayrı oluşturun.
C'de sütun boyutlarını unutmak. Çağıran kod, *returnSize değerini sonuç satırlarının sayısı olan n, (*returnColumnSizes)[j] değerini ise her satırın uzunluğu olan m olarak okur.

Sıkça sorulan sorular4

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ıra, i. sütuna taşınır. 2 × 3 boyutundaki bir matris 3 × 2 boyutuna dönüşür ve iki kez transpozunu almak matrisi başlangıçtaki hâline getirir.

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

Bu O(m × n) olur, çünkü m × n değerlerin her biri bir kez kopyalanır ve bundan daha azı yanıtı oluşturamaz. 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: O(1) ek bellek kullanarak köşegenin üstündeki her hücre için matrix[i][j] ile matrix[j][i] değerlerini yer değiştirin. Kare olmayan bir matriste sonucun şekli farklı olur; bu nedenle satır listesi kullanıyorsanız yeni bir matrise ihtiyacınız vardır.

Kare olmayan bir matrisi nasıl transpoze edersiniz?

Girdinin n satır ve m uzunluğunda satırlardan oluştuğu durumda, m satır ve n uzunluğunda satırlardan oluşan bir sonuç oluştur. Ardından her değeri result[j][i] = matrix[i][j] ile kopyala. Kare matris durumundaki köşegen fikri burada geçerli değildir, çünkü iki matrisin şekli aynı değildir.

Python

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

Test durumları

Durum 1

Durum 2

Girdi

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

Beklenen

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