【探索-中级算法】矩阵置零
参考链接：https://www.jianshu.com/p/d0017b1e38c4
原地算法：一种使用小的，固定数量的额外之空间来转换资料的算法。 当算法执行时，输入的资料通常会被要输出的部份覆盖掉。
O(mn) 的额外空间
public void setZeroes1(int[][] matrix) {
if (matrix == null || matrix[0] == null || matrix[0].length < 1) return;
// 结合额外的辅助数组来判断
// 如果 matrix[i][j] == 0 && !map[i][j] 则表示 matrix[i][j] 原本就为 0
// 如果 matrix[i][j] == 0 && map[i][j] 则表示 matrix[i][j] 是后面置为 0 的
boolean[][] map = new boolean[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0 && !map[i][j]) {
for (int k = 0; k < matrix[0].length; k++) {//先把那一横置 0
if (matrix[i][k] == 0) continue;
matrix[i][k] = 0;
map[i][k] = true;
}
for (int k = 0; k < matrix.length; k++) {//先把那一列置 0
if (matrix[k][j] == 0) continue;//如果已经为 0 则跳过
matrix[k][j] = 0;
map[k][j] = true;
}
}
}
}
}
O(m+n) 的额外空间
// 不能边修改边遍历，
// 因此先记录符合要求的
// 某一行只要有一个，那么该行全部置 0，列同理
public void setZeroes2(int[][] matrix) {
if (matrix == null || matrix[0] == null || matrix[0].length < 1) return;
boolean rw[] = new boolean[matrix.length];//记录哪几行需要被置 0
boolean cl[] = new boolean[matrix[0].length];//记录哪几列需要被置 0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
rw[i] = true;
cl[j] = true;
}
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (rw[i]||cl[j]) matrix[i][j] = 0;
}
}
}
关键点就是不能边修改边遍历，因为修改后的值后影响对于原值的判断，而且如果有某一行有一个为 0，则该行需要全部置为 0，对于列也同样如此。
O(1) 的额外空间
public static void setZeroes3(int[][] matrix) {
if (matrix == null || matrix[0] == null || matrix[0].length < 1) return;
boolean row = false;
boolean col = false;
//判断第一列是不是要置 0
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][0]==0) {
col = true;
break;
}
}
//判断第一行是不是要置 0，也需要从受元素遍历起（即 j 不能从 1 开始），如{{0,1}} 的情况
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[0][j]==0) {
row = true;
break;
}
}
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length; j++) {
if (matrix[i][j]==0) {
matrix[0][j] = 0;// 该点所在列第一个
matrix[i][0] = 0;// 该点所在行第一个
}
}
}
//要注意 c 的起始值为 1，如果从 0 开始则当 matrix[0][0] 为 0 时，
//会把第一列全部置为 0，从而影响后面的逻辑
for (int c = 1; c <matrix[0].length ; c++) {
if (matrix[0][c]==0) {//根据第一行的值来处理每一列
for (int r = 1; r < matrix.length; r++) {
matrix[r][c] = 0;
}
}
}
//r 的起始值同理
for (int r = 1; r < matrix.length; r++) {
if (matrix[r][0] == 0) {//根据第一列的值来处理每一行
for (int c = 1; c <matrix[0].length ; c++) {
matrix[r][c] = 0;
}
}
}
if (col) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][0] = 0;
}
}
if (row) {
for (int i = 0; i < matrix[0].length; i++) {
matrix[0][i] = 0;
}
}
}
基于上一解法的思想，然后用第一行第一列辅助，节省空间。
我们可以使用原矩阵的第一行和第一列来记录哪些行和列需要全部置为 0。
首先看第一行和第一列有没有 0，如果有，记录 flag 表示之后第一行或第一列需要全部置为 0；
遍历除了第一行和第一列的所有元素，如果元素为 0，则将其所在行与第一列交点的元素，其所在列与第一行
交点的元素都置为 0。
根据第一行和第一列中的 0，将其他行列的元素置为 0；
根据记录的 flag 将第一行和第一列置为 0。
算法总结，当限定了空间时，就要考虑借用已有的空间进行辅助操作。