73. Set Matrix Zeroes

73.Set Matrix Zeroes

Given amxnmatrix, if an element is 0, set its entire row and column to 0. Do itin-place.

Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Follow up:

  • A straight forward solution using O(mn) space is probably a bad idea.
  • A simple improvement uses O(m+n) space, but still not the best solution.
  • Could you devise a constant space solution?

看到这个题目第一反应是,遍历一次矩阵,开辟两个数组,如果A[m][n] ==0,分别将行m,列n放到两个数组中,最后再遍历两个数组,将对应的行、列全部置为零。但是,这样在矩阵所有元素都为零的情况下,两个数组占用的空间就需要O(m+n),正好是题目Follow up中提到的,第二种不推荐的解法。尝试好久后,想到了最后AC的办法,主要思路是:

1、既然元素所在的行、列都要置零,这里借用数学中投影的概念,将需要置零的行、列记录在第一行和第一列。即如果A[m][n] == 0,那么 将A向左投影,令A[m][0]=0,向上投影,令A[0][n]=0;

2、分别循环第一列和第一行,将为0的元素,整行或整列置为0;

3、这里要注意第一行和第一列自己就包含0的情况,最好在纸上演示一遍。

具体代码如下:

public static void setZeroes(int[][] matrix) {
        if (matrix == null || 0 == matrix.length) {
            return;
        }
        int startCol = matrix[0][0];
        int startRow = matrix[0][0];
        int col = matrix[0].length;
        int row = matrix.length;
        for (int i = 0; i < col; i++) {
            if (0 == matrix[0][i]) {
                startRow = 0;
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            if (0 == matrix[i][0]) {
                startCol = 0;
            }
            for (int j = 0; j < matrix[i].length; j++) {
                if (0 == matrix[i][j]) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < col; i++) {
            if (0 == matrix[0][i]) {
                for (int j = 0; j < row; j++) {
                    matrix[j][i] = 0;
                }
            }
        }
        for (int i = 1; i < row; i++) {
            if (0 == matrix[i][0]) {
                for (int j = 0; j < col; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (0 == startCol) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        }
        if (0 == startRow) {
            for (int i = 0; i < col; i++) {
                matrix[0][i] = 0;
            }
        }

    }

代码的后半部分:循环第一列和第一行,整行、整列置0,其实存在很多重复的置位操作(某些元素会被重复很多次置0),这里应该存在优化的可能。本人尝试多次后被leetcode的测试样例打败,暂时没想到理想的解法,后面可以做为改进点。

测试代码如下:

public static void main(String[] args) {
        int[][] martx = new int[][] { { 1, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } };
        setZeroes(martx);
        for (int[] is : martx) {
            System.out.println(Arrays.toString(is));
        }
    }

em

相关推荐