行列90度時計回り回転アルゴリズム解析

// レイヤー数 = Math.floor(n / 2) // 3×3行列 → Math.floor(3/2) = 1レイヤー // 4×4行列 → Math.floor(4/2) = 2レイヤー // 5×5行列 → Math.floor(5/2) = 2レイヤー for (let layer = 0; layer < Math.floor(n / 2); layer++)

const first = layer; // レイヤーの開始インデックス const last = n - 1 - layer; // レイヤーの終了インデックス // 例: 4×4行列のレイヤー0の場合 // first = 0, last = 4-1-0 = 3 // 処理範囲: [0,0] から [3,3] の外周

for (let i = first; i < last; i++) { const offset=i - first; // 現在位置からの相対位置 // 4つの対応する要素の座標 const topPos=[first, i]; // 上辺の要素 const rightPos=[i, last]; // 右辺の要素 const bottomPos=[last, last-offset]; // 下辺の要素 const leftPos=[last-offset, first]; // 左辺の要素 }

// 1. トップ要素を一時保存 const top = matrix[first][i]; // 2. 時計回りに4つの要素を移動 matrix[first][i] = matrix[last-offset][first]; // left → top matrix[last-offset][first] = matrix[last][last-offset]; // bottom → left matrix[last][last-offset] = matrix[i][last]; // right → bottom matrix[i][last] = top; // top → right (保存値を使用)

function rotate(matrix: number[][]): void { const n = matrix.length; // 外側から内側へレイヤーごとに処理 for (let layer = 0; layer < Math.floor(n / 2); layer++) { const first=layer; // 現在レイヤーの開始位置 const last=n - 1 - layer; // 現在レイヤーの終了位置 // レイヤーの上辺を左から右へ処理（最後の要素は除く） for (let i=first; i < last; i++) { const offset=i - first; // 現在処理中の4要素の座標 // top: matrix[first][i] 例: [0][1] // right: matrix[i][last] 例: [1][3] // bottom: matrix[last][last-offset] 例: [3][2] // left: matrix[last-offset][first] 例: [2][0] const top=matrix[first][i]; // 上要素を退避 // 時計回りに回転（left→top→right→bottom→left） matrix[first][i]=matrix[last - offset][first]; // left → top matrix[last - offset][first]=matrix[last][last - offset]; // bottom → left matrix[last][last - offset]=matrix[i][last]; // right → bottom matrix[i][last]=top; // top → right } } }