Transpose Matrix
整数の行列が行のリストとして与えられます。matrix[i][j]は、行i、列jの値です。転置行列、つまり各行を列に入れ替えた行列を返してください。行i、列jの値は、行j、列iに移動します。行列は正方行列である必要はありません。m × n行列はn × m行列になります。
関数
- matrixinteger-2d-array
- m 行 n 列の行列。各行は n 個の整数からなる m 行のリスト
- 戻り値integer-2d-array
- n × m の転置行列。m 個の整数からなる行が n 行のリスト
制約
1 ≤ m, n ≤ 1000。ここで、m = matrix.length、n = matrix[i].lengthm × n ≤ 5000- すべての行の長さは同じで、
nです。 -1000 ≤ matrix[i][j] ≤ 1000
例
- 入力
- matrix = [[1, 2, 3], [4, 5, 6]]
- 出力
- [[1, 4], [2, 5], [3, 6]]
- 説明
- 最初の行
[1, 2, 3]は最初の列になり、[4, 5, 6]は2番目の列になります。結果を行ごとに読むと、[1, 4]、[2, 5]、[3, 6]となります。2 × 3 の行列が 3 × 2 の行列になりました。
- 入力
- matrix = [[1, 2], [3, 4]]
- 出力
- [[1, 3], [2, 4]]
- 説明
- 正方行列では、対角線上の値 1 と 4 はそのままの位置にあり、対角線から外れた2つの値は入れ替わります。2は行0、列1から行1、列0へ移動し、3は反対方向へ移動します。
提出時に隠しテスト+15件
発展問題
行ごとに並んだm × n個の値を持つ1次元配列として、行列が格納されているとします。別の配列を使わずに、その配列の中で長方形行列を転置できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
入力が
m行n列の場合、答えは何行何列になりますか？値が前後でどこにあるかを比較します。行
i、列jにある値は、行j、列iに移動します。それぞれに
m個の値を持つn行の結果を作成し、入力のすべてのセルをループして、matrix[i][j]をresult[j][i]にコピーします。
解説
転置はアドレスを純粋に入れ替える操作です。(i, j)にある値は(j, i)に移動し、計算は何も行いません。重要なのは、形状を正しくすることです。行のリストとして格納された正方形でない行列は、その場で転置できません。転置後の行列は、長さがmの行がn行ではなく、長さがnの行がm行になるため、入れ替えたサイズの新しい行列を作って値を埋めます。
行列を列ごとに読み取ります
考え方
答えの j 行目は、入力の j 列目を上から下へ読んだものです。そのため、答えを1行ずつ作ります。0 から n-1 までの各列 j について、matrix[0][j]、matrix[1][j]、さらに下へ進んで matrix[m-1][j] までを集め、そのリストを次の行として追加します。
[[1, 2, 3], [4, 5, 6]] の場合、列0は1、次に4、列1は2、次に5、列2は3、次に6と読みます。答えは [[1, 4], [2, 5], [3, 6]] で、m = 2 個の値を持つ行が n = 3 行あります。
各値は一度読み取られ、一度書き込まれるため、時間計算量は O(m × n) で、結果には O(m × n) の領域が必要です。コストがかかるのはアクセスのパターンです。新しい行を1行作るたびに入力のすべての行にアクセスするため、1行に沿って読み進めるのではなく、行から行へ飛び移ります。
アルゴリズム
mを行数、nを1行の長さとします。0からn-1までの各列jについて、空のリストを作成します。iを0からm-1まで変えながら、各iについてmatrix[i][j]をそのリストに追加します。- そのリストを行
jとして結果に追加し、最後の列の後に結果を返します。
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各セルを鏡映して、新しい n × m のグリッドを埋める
考え方
まず形を決めてから、中身を埋めます。答えは長さ m の行が n 個あるので、最初にそのグリッドを作成します。次に、入力を自然な順序、つまり行ごとに左から右へ読み取り、各値をインデックスを入れ替えた位置に格納します: result[j][i] = matrix[i][j]。
転置とは2つのインデックスを入れ替えることそのものなので、この規則は正しいです。正方形の例 [[1, 2], [3, 4]] では、対角線上の1と4は同じ位置に残り、2は (0, 1) から (1, 0) へ、3は (1, 0) から (0, 1) へ移動し、結果は [[1, 3], [2, 4]] になります。
m × n 個の値をそれぞれ1回ずつコピーするため、時間計算量は O(m × n) です。また、新しいグリッドに必要な O(m × n) の空間は、いずれにせよ出力に必要です。入力を行に沿って読み取ると、メモリに格納されている順序でアクセスでき、結果の各行は最終的なサイズで一度だけ作成されます。
アルゴリズム
mを行数、nを1行の長さとします。n行を持ち、それぞれにm個の値を格納するresultを作成します。- 入力の各行
iと各列jについて、result[j][i] = matrix[i][j]を設定します。 resultを返します。
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
落とし穴と境界ケース
誤答のほとんどは、値ではなく形状に起因します。
- 元の形状のまま結果を作成する。
m行n列の結果が機能するのは、入力が正方行列の場合のみです。2 × 3 の例では、result[2][0]と書くと範囲外になります。結果は、長さmの行をn個持つ必要があります。 - 正方行列でない行列をその場で入れ替える。
matrix[i][j]とmatrix[j][i]の入れ替えが機能するのはm = nの場合のみです。その場合でも、ループの対象は対角線より上のセル（j > i）だけにする必要があります。そうしないと、各ペアが2回入れ替わり、行列が元に戻ってしまいます。 - 同じ行オブジェクトを共有する。Python では、
[[0] * m] * nは同じリストへの参照をn個作成するため、1つのセルに書き込むと列全体に書き込まれます。各行を個別に作成してください。 - C で列のサイズを忘れる。呼び出し側は、
*returnSizeを結果の行数nとして、(*returnColumnSizes)[j]を各行の長さmとして読み取ります。
よくある質問4
行列の転置とは何ですか？
行と列を入れ替えて得られる行列です。行 i、列 j の値は、行 j、列 i に移動します。2 × 3 行列は 3 × 2 行列になり、2回転置すると元に戻ります。
行列の転置の時間計算量はどれくらいですか？
m × n 個の値がそれぞれ一度ずつコピーされ、それより少ない処理では答えを出せないため、O(m × n) です。新しい行列には O(m × n) の領域が必要で、これは出力自体のサイズです。
行列をインプレースで転置できますか？
正方行列の場合は、はい。対角線より上にあるすべてのセルについて、追加メモリ O(1) で matrix[i][j] と matrix[j][i] を入れ替えます。正方形でない行列は結果の形状が異なるため、行のリストを使う場合は新しい行列が必要です。
正方行列でない行列を転置するにはどうすればよいですか？
入力が長さnの行をm個持つ場合、長さmの行をn個持つ結果を作成します。その後、result[j][i] = matrix[i][j]を使ってすべての値をコピーします。2つの行列の形状は一致しないため、正方行列の場合の対角線の考え方は当てはまりません。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def transpose(matrix):
# ここにコードを書いてくださいケース1
ケース2
入力
matrix = [[1, 2, 3], [4, 5, 6]]
期待値
[[1, 4], [2, 5], [3, 6]]