1

这是一个面试问题：在一个大小为 mxn 的二维数组中，对于每个值为 0 的元素，将该元素所在的整个行和列设置为零，其余元素保持不变。

我可以想到的方法是遍历数组中的每个元素，每次遇到零时，我用零标记整个行和列。但这是幼稚的，请提出任何改进建议。

4

5 回答 5

3

如果允许额外的空间。只需维护两个标志数组。

一个代表行，另一个代表列。所有默认值设置为 1。

扫描您的原始矩阵，假设您在 x 行和 y 列找到一个 0。只需设置 row[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 回答
2

你的算法的复杂性是二次的。如果整个矩阵最初全为零，您将擦除每一列n_rows时间和每一行n_columns时间。

更好的方法是维护布尔数组的大小m，并n指示哪些行和列需要归零。遍历矩阵的元素，适当地填充布尔数组。完成后，遍历布尔数组并根据您在其中找到的值进行零填充。这样，每个元素最多清零两次。

于 2013-09-05T16:07:07.803 回答
1

如果您在进行过程中归零，您将在找到第一个之后清除每一行和每一列。只需在清零行和列之前找到并记录所有零。或者，创建二维数组的副本并修改第二个，同时查看第一个以供参考。

于 2013-09-05T16:02:23.987 回答
1

允许额外的空间？如果是这样，给定 mxn 矩阵，我们为行维护两个大小为 m 的位图，以指示何时应将行归零，对于列也类似。位图可以很容易地检查 O(1) 中是否已经设置了行或列。

Pass 1：优化矩阵的迭代，在遍历矩阵的元素寻找零的同时，当我们发现零是位置 (i,j) 时，我们可以设置两个位图中的对应位并停止迭代该行进一步的元素。（毕竟我们将整行和整列归零）。

第 2 步：现在我们有了两个位图，循环遍历它们，将行和列归零。如果您想在将行中的元素归零时非常优化（如果归零是一项代价高昂的操作），则可以跳过相应的列位是否已设置，在遍历列时最终归零。

编辑：您可以一次性完成，只需为列单独设置一个位图，如果找到零则遍历矩阵，将整行和列设置为零，设置列位图位置，然后继续下一行. 在迭代后续行时跳过设置了位的列

于 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 回答