M×Nの行列について、要素が0であればその行と列の全てを0にするようなアルゴリズムを考えます。
「解法」
行列の全ての要素を順番に調べて、0があればその行と列を0にしていうだけの一見簡単そうに見えるアルゴリズムですが、その場で行と列を0で埋める処理をしてしまうと、あっという間に全ての要素が0になってしまうでしょう。
この問題を解決するにはもう一つ行列を用意し、0で埋める場所を記録していく方法が考えられますが、行列の全ての要素を2回走査する必要があります。このアルゴリズムではO(MN)のメモリが必要になります。
しかし、本当にO(MN)も必要なのでしょうか? 答えはノーです。全ての列と行を0にセットするのですから、行列の詳細な要素を正確に追っていく必要はないのです。必要な情報は「二列目のどこかに0がある」とか「4行目のどこかに0がある」のようなことだけなのです。そして、0が含まれているわかっている列・行をとにかく0で埋めるだけ。
以下のコードは今説明したアルゴリズムを実装したものです。列と行のそれぞれに関しての配列を使い、それらに0が含まれるかどうかを記録しておきます。その情報をもとに、列か行に0が含まれていれば、そこを埋めていくのです。
Java
1public void setZeros(int[][] matrix) { 2 boolean[] row = new boolean[matrix.length]; 3 boolean[] column = new boolean[matrix[0].length]; 4 5 //0を含む行及び列のインデックスを保持 6 for(int i = 0;i < matrix.length;i++) { 7 for(int j = 0;j< matrix[0].length;j++) { 8 if(matrix[i][j] == 0) { 9 row[i] = true; 10 column[j] = true; 11 } 12 } 13 } 14 15 //行iまたは列jが0を含んでいれば、各要素を全て0にする 16 for(int i = 0;i < matrix.length;i++) { 17 for(int j = 0;j < matrix[0].length;j++) { 18 if(row[i]||column[j]) { 19 matrix[i][j] = 0; 20 } 21 } 22 } 23 }
上の文章の「この問題を解決するにはもう一つ行列を用意し、0で埋める場所を記録していく方法が考えられますが、行列の全ての要素を2回走査する必要があります。このアルゴリズムではO(MN)のメモリが必要になります。」の部分がよくわかりません。
上に示したアルゴリズムでも二回走査していませんか?
また、
Java
1public void setZeros2(int[][] matrix) { 2 int[][] newMatrix = new int[matrix.length][]; 3 for(int i = 0;i<matrix[0].length;i++){ 4 newMatrix[i] = Arrays.copyOf(matrix[i], matrix[0].length); 5 6 //以下ほぼ同様のコード 7 } 8 9 }
このコードのようにまず配列をコピーして、boolean型の配列を使って、0があるかどうかを検出して、その結果を用いて、行及び列を0にするという方法では、そうでないコードと比べて余計にO(MN)のメモリが必要となるという意味なのでしょうか?
回答お願いします。
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。