行列の回転

問題

N*Nの行列を90度回転させる

考え方

あまりたくさんのメモリを使いたくないので、１つの値だけを保持して回転させたい。 回転させると(i, j) -> (j, N-i)に移る。移った先を考えると、

• (j, N-i)-> (N-i, N-j)
• (N-i, N-j) -> (N-j, i)
• (N-j, i) -> (i, j)

まずは4 * 4の行列から考えてみる。 回転させると(0, 0) -> (0, 3)に移る。この点を循環させて、次に(0, 1), (0,2)と行うが、(0, 3)までやるとすでに回転させたものがあることに気づく。 つまり、列はNまでは行わない。 また、次の行に進もうとすると、初めの列はすでに回転したものであるから、その次の列から行う必要がある。

以上のことに注意すると、行iに対して、列はi -> N/2まで回転を行う。 また、４点を回転させるときに、どれか１つだけメモリに入れておいて、回転させる。

計算量

全ての点をみる必要があるので、時間計算量はO(N)である。追加で必要な空間計算量は1で済む。

コード例

#include<iostream>

using namespace std;
void rotate(int N, int **matrix){
    int i, j, start, end;
    int temp;
    i = 0;
    end = N;
    for(start=0; start<N/2; start++){
        // 列の動く量
        end--;
        for(j=start; j<end; j++){
            temp = matrix[N-1-j][i];
            matrix[N-1-j][i] = matrix[N-1-i][N-1-j];
            matrix[N-1-i][N-1-j] = matrix[j][N-1-i];
            matrix[j][N-1-i] = matrix[i][j];
            matrix[i][j] = temp;
        }
        i++;//行を次に進める
    }
}

int main(void){
    int i, j, N;
    N = 5;
    int **matrix = (int**)malloc(N*sizeof(int*));
    matrix[0] = (int*)malloc(N*N*sizeof(int));
    for(i=0; i<N; i++){
        matrix[i] = matrix[0] + i*N;
    }
    for(i=0; i<N; i++){
        for(j=0; j<N; j++){
            matrix[i][j] = i+j;
        }
    }
    cout << "元の行列" <<  endl;
    for(i=0; i<N; i++){
        for(j=0; j<N; j++){
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    rotate(N, matrix);
    cout << "回転させた行列" <<  endl;
    for(i=0; i<N; i++){
        for(j=0; j<N; j++){
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}