题目：

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

Did you use extra space?

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?

思路：

1) O(mn)解法，拷贝一份matrix，然后对照这个matrix来设置原matrix的各个元素

2) O(m+n)解法，两个一维Boolean数组Rows和Columns，大小分别为m和n，如果元素（i，j）为0，则设置Rows[i]=true, Columns[j] = true。之后根据Rows和Columns中的值来对每行和每列进行设置为0.

3) 在方法二的基础上，借用matrix的第一行和第一列来表示相应的列和行是否为0，但这个时候需要对第一行和第一列进行特殊化处理，我们就用两个Boolean变量来应对。

package array;public class SetMatrixZeroes {    public void setZeroes(int[][] matrix) {        boolean firstRow = false;        boolean firstColumn = false;        int m = matrix.length;        int n = matrix[0].length;        for (int i = 0; i < m; ++i) {            for (int j = 0; j < n; ++j) {                if (matrix[i][j] == 0) {                    if (i == 0) firstRow = true;                    if (j == 0) firstColumn = true;                    matrix[i][0] = matrix[0][j] = 0;                }            }        }                for (int i = 1; i < m; ++i) {            for (int j = 1; j < n; ++j) {                if (matrix[i][0] == 0 || matrix[0][j] == 0)                    matrix[i][j] = 0;            }        }                if (firstRow) {            for (int i = 0; i < n; ++i)                matrix[0][i] = 0;        }                if (firstColumn) {            for (int i = 0; i < m; ++i)                matrix[i][0] = 0;        }    }        public static void main(String[] args) {        // TODO Auto-generated method stub        int[][] matrix = { { 1, 0, 1 }, { 1, 1, 1 }, { 0, 1, 1 } };        SetMatrixZeroes s = new SetMatrixZeroes();        s.setZeroes(matrix);    }}