Rotate Image
各行が1つのリストになっている、整数からなる n × n のグリッドが与えられます。これを時計回りに90度回転させて返してください。最上段は最も右の列になり、その下の行はその左隣の列になり、以下同様です。つまり、(i, j) の値は (j, n-1-i) に移動します。グリッドはその場で変更してもかまいません。グリッドを返してください。
関数
- matrixinteger-2d-array
- 正方形のグリッド。各行に1つの内側のリスト
- 戻り値integer-2d-array
- 行列が時計回りに90度回転した
制約
n == matrix.length == matrix[i].length1 ≤ n ≤ 70-1000 ≤ matrix[i][j] ≤ 1000
例
- 入力
- matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
- 出力
- [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
- 説明
- 最初の行である3 7 1は、上から下に読むと最後の列になります。最初の列である3 9 4は、下から上に読むと最初の行
[4, 9, 3]になります。中央の値5はそのままです。
- 入力
- matrix = [[1, 0, 0, 2], [0, 5, 6, 0], [0, 7, 8, 0], [3, 0, 0, 4]]
- 出力
- [[3, 0, 0, 1], [0, 7, 5, 0], [0, 8, 6, 0], [4, 0, 0, 2]]
- 説明
- 各隅は時計回りに1つ移動します。1は右上へ、2は右下へ、4は左下へ、3は左上へ移動します。内側の2 × 2ブロックも同じ方向に回転します。
発展問題
行列をインプレースで180度回転させる2つの手順は何ですか？また、要素の交換を1回のパスで行えますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
1つの値を追跡しましょう。時計回りに4分の1回転させた後、行0、列0の値はどこに移動しますか？行0の残りの値はどこに移動しますか？
行
iは列n-1-iになります。同じ行列内で値を新しい位置に直接書き込むと、まだ移動していない値が壊れてしまうため、値のペアを入れ替えるだけの、より簡単な2つの操作を考えてみましょう。まず転置します。主対角線より上の各値を、その鏡像となる下の値と入れ替えます。次に、各行を逆順にします。2 × 2 行列で、結果が反時計回りではなく時計回りになったことを確認してください。
解説
各値の移動先は数式で表せます。(i, j) は (j, n-1-i) に移動します。難しいのは、2つ目の行列を使わずに値を移動することです。値を新しいセルに書き込むと、まだ移動していない値が上書きされてしまうためです。転置してから行を反転すると、要素のペア交換だけで同じ90度回転ができます。
回転したコピーを作成する
考え方
行 i は列 n-1-i になり、行内の位置 j にある値は、その列を下に進んだ位置 j、つまり行 j に入ります。したがって result[j][n-1-i] = matrix[i][j] となります。最初の例では、行 2、列 0 の 4 は行 0、列 0 に移動するため、答えは 4 から始まります。
値は4つずつの循環に沿って移動するため、その場で書き込むと、値が移動する前に別の値を消してしまいます。3 が右上隅の 1 を上書きしてしまいます。コピーには n² 個の追加セルが必要で、n = 70 の場合は 4,900 個です。
アルゴリズム
n × nの結果行列を作成します。- 各行
iと列jについて、matrix[i][j]をresult[j][n-1-i]にコピーします。 - 結果を返します。
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転置してから、各行を反転する
考え方
転置によって(i, j)は(j, i)に移動し、行を反転すると列cは列n-1-cに移動します。この2つを組み合わせると(i, j)は(j, n-1-i)に移動し、これは回転後の位置とまったく同じです。
どちらの操作も、複数のペアを入れ替える処理なので、インプレースで実行できます。転置では、matrix[i][j]とmatrix[j][i]はそれぞれ相手のセルに入るため、1回の入れ替えで両方が完了します。j > iのペアだけを入れ替えてください。そうしないと、すべてのペアが元に戻ってしまいます。行の反転では、両端の要素を入れ替えながら内側へ進みます。
最初の例では、転置すると[[3, 9, 4], [7, 5, 8], [1, 2, 6]]になります。各行には、元の列が入っています。各行を反転すると答えになります。
転置ではn(n-1)/2回、反転ではn·⌊n/2⌋回の入れ替えを行うため、追加メモリをいくつかの変数分だけ使い、処理量はO(n²)です。R版では、まず入力をRの行列にコピーするため、追加メモリはO(n²)です。
アルゴリズム
- 主対角線より上にあるすべてのセル
(i, j)（j > i）について、その値をセル(j, i)と入れ替えます。 - 各行で、最初と最後の値を入れ替え、両端から中央に向かって進みます。
- 行列を返します。
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
落とし穴と境界ケース
jを0から開始して転置する。各ペアが2回入れ替わるため、転置が相殺され、結果は行を逆順にしただけの鏡像になる。- 転置する前に反転する。その順序では、行列が反時計回りに回転する。2 × 2のテストで確認できる。
[[1, 2], [3, 4]]は[[3, 1], [4, 2]]になる必要がある。 - 同じ行列に
matrix[j][n-1-i] = matrix[i][j]を書き込む。移動していない値が移動先のセルにまだ残っており、その値は失われる。 n-1-iの代わりにn-iを使う。0始まりのインデックスでは最後の列はn-1なので、i = 0の場合、n-iは配列の範囲を超える。
よくある質問3
行列を回転させる時間計算量と空間計算量はどれくらいですか？
n × n 行列の回転には、ほぼすべての値を一度移動させる必要があるため、O(n²) の時間がかかります。転置して反転する方法では、追加の領域を O(1) しか使いません。回転後のコピーを作成する場合も O(n²) の時間がかかりますが、追加の領域を O(n²) 使います。
行列を反時計回りに回転させるにはどうすればよいですか？
2つの手順の順序を入れ替えます。まず各行を逆順にし、その後で転置します。転置してから行の順序を逆にしてもかまいません。どちらの場合も、(i, j) にある値は最終的に (n-1-j, i) に移動します。
4つの値を一度に移動して、行列を回転させることはできますか？
はい。中心以外の各値は、4つのセルからなるサイクルに属します：(i, j)、(j, n-1-i)、(n-1-i, n-1-j)、(n-1-j, i)。リングごとに、各サイクルの1つの値を変数に保持し、残りの3つを移動します。計算量は同じく時間がO(n²)、空間がO(1)ですが、間違えやすいインデックス計算が増えます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def rotateImage(matrix):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
期待される出力
[[4, 9, 3], [8, 5, 7], [6, 2, 1]]