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].lengthです。m × n ≤ 5000- すべての行の長さは
nで同じです。 -1000 ≤ matrix[i][j] ≤ 1000
例
- 入力
- matrix = [[1, 2, 3], [4, 5, 6]]
- 出力
- [[1, 4], [2, 5], [3, 6]]
- 説明
- 行
[1, 2, 3]は1列目になり、[4, 5, 6]は2列目になります。行ごとに読むと、結果は[1, 4]、[2, 5]、[3, 6]となり、3 × 2 の行列です。
- 入力
- matrix = [[1, 2], [3, 4]]
- 出力
- [[1, 3], [2, 4]]
- 説明
- 対角線上の値1と4はそのままです。残りの2つは位置を入れ替えます。2は行0、列1から行1、列0へ移動し、3は反対方向へ移動します。
発展問題
行ごとに並べたm × n個の値を持つ1つのフラットな配列に、行列が格納されているとします。2つ目の配列を使わずに、その配列内で長方形行列を転置できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
入力に
m行とn列がある場合、答えは何行何列になりますか？値が変換前と変換後でどこに位置するかを比較します。行
i、列jにある値は、行j、列iに移動します。それぞれに
m個の値を持つn行の結果を作成し、入力のすべてのセルをループして、matrix[i][j]をresult[j][i]にコピーします。
解説
転置では何も計算しません。(i, j)の値が(j, i)に移動します。作業の中心は形状です。結果は長さmの行をn個持つため、正方形でない行のリストはその場で転置できません。入れ替えたサイズの新しい行列を作り、値を埋めます。
行列を列ごとに読み取ります
考え方
答えのj行目は、入力のj列目を上から下へ読んだものです。[[1, 2, 3], [4, 5, 6]]では、0列目を読むと1、次に4となるため、答えの最初の行は[1, 4]です。
各値は一度ずつ読み取られ、一度ずつ書き込まれます。時間計算量はO(m × n)、結果のための空間計算量はO(m × n)です。新しい各行を作るときは、入力の各行をまたいで移動することになります。これは、1行に沿って読み取るよりもメモリをたどる速度が遅い方法です。
アルゴリズム
mを行数、nを1行の長さとします。0からn-1までの各列jについて、空のリストを作成します。iが0からm-1までの各値について、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 グリッドを埋める
考え方
まず n × m の結果を作成し、次に入力を保存されている順序で行ごとに読み込み、各値をインデックスを入れ替えた位置に格納します。result[j][i] = matrix[i][j]。転置とは、すべてのセルに対して一度ずつインデックスを入れ替えることだからです。
各値は一度だけコピーされるため、時間計算量は 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
落とし穴と境界ケース
- 入力と同じ形で結果を作ること。2 × 3 の例では、
result[2][0]と書くと範囲外になります。結果には、長さがmの行がn個必要です。 matrix[i][j]とmatrix[j][i]をその場で入れ替えること。これはm = nの場合に限り、さらにj > iのセルに限って機能します。すべてのセルを走査するループでは各ペアを2回入れ替えるため、行列は元の状態に戻ります。- Python では、
[[0] * m] * nは1つのリストへの参照をn個作るため、1つのセルに書き込むと列全体に反映されます。各行を個別に作成してください。 - C では、呼び出し元は
*returnSizeを結果の行数nとして読み取り、(*returnColumnSizes)[j]を各行の長さmとして読み取ります。
よくある質問3
行列の転置とは何ですか？
行と列を入れ替えて得られる行列です。行 i、列 j の値は、行 j、列 i に移動します。2 × 3 行列は 3 × 2 行列になり、転置を2回行うと元に戻ります。
行列の転置の時間計算量はどれくらいですか？
O(m × n): m × n 個の値をそれぞれ1回ずつコピーし、それより少ない操作では答えを生成できません。新しい行列には、出力そのもののサイズである O(m × n) の領域が必要です。
行列をインプレースで転置できますか？
正方行列の場合は可能です。対角線より上にあるすべてのセルについて、matrix[i][j]とmatrix[j][i]を入れ替えればよく、追加メモリはO(1)です。正方形でない行列は形状が変わるため、行のリストを使う場合は新しい行列が必要です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def transpose(matrix):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
matrix = [[1, 2, 3], [4, 5, 6]]
期待される出力
[[1, 4], [2, 5], [3, 6]]