行列の変換

問題

M*N の行列において、(i, j)が0なら、その行iと列jを全て０にする。

考え方

(0, 0)から０の成分を見つけて、変換していくと全て０に変わってしまうので、まずは０の成分のある位置を格納する。 何個あるかわからないので、可変長配列(C++ではvector型)を用いる。

同じiがあっても意味がないので、iとj別々に格納していき、重複がないようにする。

計算量

0を探すのに。 行の0の数をK、列の0の数をLとすると、 0に入れ替える作業はKN+LM。 なので、時間計算量はになる。空間計算量は0のindexを記録するだけなのでである。

コード例

#include<iostream>
#include<vector>
using namespace std;

void to_zero(int M, int N, int **matrix){
    //まずは０が入っているindexを記録する。O(N^2)
    int i, j;
    vector<int> x, y;
    x = {};
    y = {};
    for(i=0; i<M; i++){
        for(j=0; j<N; j++){
            if(matrix[i][j]==0){
                x.push_back(i);
                //jからでる。
                break;
            }
        }
    }
    for(j=0; j<N; j++){
        for(i=0; i<M;  i++){
            if(matrix[i][j]==0){
                y.push_back(j);
                // iからでる
                break;
            }
        }
    }
    // x, y用いてmatrixを変更する
    for(i=0; i<x.size(); i++){
        for(j=0; j<N; j++){
            matrix[x[i]][j] = 0;
        }
    }
    for(j=0; j<y.size(); j++){
        for(i=0; i<M; i++){
            matrix[i][y[j]] = 0;
        }
    }
}

int main(void){
    int i, j, M, N;
    M = 5;
    N = 4;
    int **matrix = (int**)malloc(M*sizeof(int*));
    matrix[0] = (int*)malloc(M*N*sizeof(int));
    for(i=0; i<M; i++){
        matrix[i] = matrix[0] + i*N;
    }
    for(i=0; i<M; i++){
        for(j=0; j<N; j++){
            matrix[i][j] = i+j-i*j;
        }
    }
    cout << "元の行列" <<  endl;
    for(i=0; i<M; i++){
        for(j=0; j<N; j++){
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    // main
    to_zero(M, N, matrix);
    cout << "変更した後の行列" <<  endl;
    for(i=0; i<M; i++){
        for(j=0; j<N; j++){
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

結果

 > ./a.out
元の行列
0 1 2 3
1 1 1 1
2 1 0 -1
3 1 -1 -3
4 1 -2 -5
変更した後の行列
0 0 0 0
0 1 0 1
0 0 0 0
0 1 0 -3
0 1 0 -5

参考

問題は 世界で闘うプログラミング力を鍛える本 | マイナビブックス から。