1

これはインタビューの質問です: サイズ mxn の 2 次元配列で、値がゼロの各要素について、この要素が配置されている行と列全体をゼロに設定し、残りの要素はそのままにしておきます。

私が思いついた方法は、配列内の各要素を繰り返し処理することでした。ゼロに遭遇するたびに、行と列全体をゼロでマークします。しかし、これは素朴です。改善を提案してください。

4

5 に答える 5

3

余分なスペースが許可されている場合。フラグの 2 つの配列を維持するだけです。

1 つは行を表し、もう 1 つは列を表します。すべてのデフォルト値は 1 に設定されています。

元の行列をスキャンして、行 x と列 y に 0 があると仮定します。行[x] = 0を設定するだけです。列[y] = 0;

次に、マトリックスを再度スキャンします

for ( int i = 0; i < height; ++i )
  for ( int j = 0; j < width; ++j )
    M[i][j] = M[i][j] * row[i] * column[j];

次に、行列 M を変更します

于 2013-09-05T19:01:03.337 に答える
1

進むにつれてゼロにすると、最初に見つけた行と列の後にすべての行と列がクリアされます。行と列をゼロにする前に、すべてのゼロを見つけて記録するだけです。または、2 次元配列のコピーを作成し、1 番目の配列を参照しながら 2 番目の配列を変更します。

于 2013-09-05T16:02:23.987 に答える
1

余分なスペースは許可されていますか? その場合、mxn 行列が与えられた場合、行をいつゼロにするかを示すために、行のサイズが m の 2 つのビットマップを維持し、列についても同様に維持します。ビットマップを使用すると、行または列が既に設定されているかどうかを O(1) で簡単に確認できます。

パス 1: マトリックスの最適化された反復。マトリックスの要素を反復しながらゼロを探します。ゼロが位置 (i,j) であることがわかった場合、2 つのビット マップに対応するビットを設定し、その行の反復を停止できます。さらなる要素。（結局のところ、行と列全体をゼロにしています）。

パス 2: これで 2 つのビット マップが得られました。これらをループして、行と列をゼロにします。行内の要素をゼロ化するときに非常に最適化したい場合 (ゼロ化がコストのかかる操作である場合)、対応する列ビットが設定されている場合はスキップできます。

編集：ゼロを見つけた場合はマトリックスを反復処理しながら、列だけのビットマップを持つだけで1回のパスでそれを行うことができ、その行と列全体をゼロに設定し、列のビットマップ位置を設定し、次の行に進みます. 後続の行を繰り返しながら、ビットが設定された列をスキップします

于 2013-09-05T16:23:26.013 に答える
0 
package helloWorld;
import java.util.HashMap;
import java.util.Map;

public class Solution {

    public static int[][] myFunction(int[][] matrix) {

        // find all rows and columns that contains zeros
        // keep their indexes in hashMap
        // loop over the matrix and check if you have row and column in your  
        // hashmap if yes make them zero, and also mark the row/column as  
        // already zeroed

        Map<String, Boolean> map = new HashMap<String, Boolean>();
        int length = matrix[0].length;
        int heigth = matrix.length;
        for (int i = 0; i < heigth; i++) {
            for (int j = 0; j < length; j++) {
                if (matrix[i][j] == 0) {
                    // mark and keep Row in Map
                    if (!map.containsKey("R" + i)) {
                        map.put("R" + i, false);
                    }
                // mark and keep column in Map
                if (!map.containsKey("C" + j)) {
                    map.put("C" + j, false);
                    }
                }
            }
        }
        for (int i = 0; i < length; i++) {
            //check if row need to be zeroed and if yes zero it and Mark it    
            //as done 
            if (map.containsKey("R" + i) && !map.get("R" + i)) {
                for (int j = 0; j < length; j++) {
                   matrix[i][j] = 0;
                }
                map.put("R" + i, true);
            }
            //check if column need to be zeroed and if yes zero it and Mark   
            //it as done 
            if (map.containsKey("C" + i) && !map.get("C" + i)) {
                for (int j = 0; j < heigth; j++) {
                    matrix[j][i] = 0;
                }
                map.put("C" + i, true);
            }
       }

       return matrix;
    }

    public static void main(String[] args) {

        int[][] matrix = { { 1, 2, 0, 7, 6 }, { 1, 0, 8, 7, 5 }, { 1, 2, 1,   
        7,-1 }, { 1, 2, 3, 4, 0 } };
        print(matrix);
        System.out.println("#####################################");
        matrix=myFunction(matrix);
        print(matrix);
    }

    public static void print(int[][] matrix) {
        int h = matrix.length;
        int l = matrix[0].length;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < l; j++) {
                System.out.print(" " + matrix[i][j] + " ");
            }
           System.out.println();
        }
    }
}
于 2016-07-15T18:52:13.787 に答える