準(zhǔn)備開一個(gè)力扣解題的系列，督促自己每天刷題，就從今天開始。
原題
給定一個(gè) m x n 的矩陣，如果一個(gè)元素為 0，則將其所在行和列的所有元素都設(shè)為 0。請(qǐng)使用原地算法。
示例 1:
輸入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
輸出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2:
輸入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
輸出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
進(jìn)階:
- 一個(gè)直接的解決方案是使用 O(mn) 的額外空間，但這并不是一個(gè)好的解決方案。
- 一個(gè)簡(jiǎn)單的改進(jìn)方案是使用 O(m + n) 的額外空間，但這仍然不是最好的解決方案。
- 你能想出一個(gè)常數(shù)空間的解決方案嗎？
原題url:https://leetcode-cn.com/problems/set-matrix-zeroes/
解法
其實(shí)題目本身不難，只要判斷出哪些數(shù)字是0，將其所在行和列記錄一下， 最終全部置0即可，關(guān)鍵在于你所需要消耗的空間是多少。
用一個(gè)數(shù)字
首先我想到的是用一個(gè)數(shù)字進(jìn)行表示，用二進(jìn)制表示，一共m + n位，其中前m位表示行，后n位表示列，矩陣中哪個(gè)數(shù)字為0，則其行列所在位的數(shù)字為1，也就是加上相應(yīng)的二進(jìn)制數(shù)。為了不重復(fù)添加，可以用&進(jìn)行判斷。來(lái)看看代碼是什么：
class Solution {
public void setZeroes(int[][] matrix) {
// 轉(zhuǎn)化為二進(jìn)制后，前m位表示列，后n位表示行
int temp = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] != 0) {
continue;
}
// 第j列是否已經(jīng)被設(shè)置為0
int num = 1 << (matrix.length + j);
if ((temp & num) != num) {
// 如果沒有，則加上
temp += num;
}
// 第i行是否已經(jīng)被設(shè)置為0
num = 1 << i;
if ((temp & num) != num) {
// 如果沒有，則加上
temp += num;
}
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
// 第j列是否已經(jīng)被設(shè)置為0
int numCol = 1 << (matrix.length + j);
// 第i行是否已經(jīng)被設(shè)置為0
int numRow = 1 << i;
if ((temp & numRow) == numRow || (temp & numCol) == numCol) {
// 如果有，則設(shè)置當(dāng)前值為0
matrix[i][j] = 0;
}
}
}
}
}
理論上沒什么問題，提交之后報(bào)錯(cuò)。當(dāng)m和n很大時(shí)，數(shù)字會(huì)很大，這個(gè)時(shí)候temp會(huì)越界。我想著是不是求2的冪用Math.pow()，并且 temp 的類型改為 long ，是不是就可以了，說(shuō)干就干：
class Solution {
public void setZeroes(int[][] matrix) {
// 轉(zhuǎn)化為二進(jìn)制后，前m位表示列，后n位表示行
long temp = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] != 0) {
continue;
}
// 第j列是否已經(jīng)被設(shè)置為0
long num = (long)Math.pow(2, matrix.length + j);
if ((temp & num) != num) {
// 如果沒有，則加上
temp += num;
}
// 第i行是否已經(jīng)被設(shè)置為0
num = (long)Math.pow(2, i);
if ((temp & num) != num) {
// 如果沒有，則加上
temp += num;
}
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
// 第j列是否已經(jīng)被設(shè)置為0
long numCol = (long)Math.pow(2, matrix.length + j);
// 第i行是否已經(jīng)被設(shè)置為0
long numRow = (long)Math.pow(2, i);
if ((temp & numRow) == numRow || (temp & numCol) == numCol) {
// 如果有，則設(shè)置當(dāng)前值為0
matrix[i][j] = 0;
}
}
}
}
}
好吧，依然不可以，看來(lái)確實(shí)很大，最終還是溢出變成負(fù)數(shù)了。看來(lái)得另尋他法了。
利用矩陣本身
如果1個(gè)數(shù)字不夠，那么多來(lái)幾個(gè)數(shù)字應(yīng)該也是不夠用的，而且如果用的太多也可能會(huì)增長(zhǎng)到m + n，空間依舊比較多。這個(gè)時(shí)候我也想不出來(lái)，看了看別人的解法，讓我頓時(shí)領(lǐng)悟——利用矩陣本身。
就是利用矩陣的第一行和第一列來(lái)記錄需要置零的行和列，至于第一行和第一列是否需要置零，則可以單獨(dú)拿兩個(gè) boolean 對(duì)象來(lái)表示。（怎么好的思路，為啥我就是沒想到呢）來(lái)看看代碼：
class Solution {
public void setZeroes(int[][] matrix) {
// 用第一行和第一列表示當(dāng)前行和當(dāng)前列是否需要置0
// 單獨(dú)計(jì)算第一行和第一列是否需要置0
int row = matrix.length;
int col = matrix[0].length;
// 第一行是否需要置0
boolean row0 = false;
for (int i = 0; i < col; i++) {
if (matrix[0][i] == 0) {
row0 = true;
break;
}
}
// 第一列是否需要置0
boolean col0 = false;
for (int i = 0; i < row; i++) {
if (matrix[i][0] == 0) {
col0 = true;
break;
}
}
// 判斷每一行每一列是否需要置0
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (matrix[i][j] != 0) {
continue;
}
matrix[i][0] = matrix[0][j] = 0;
}
}
// 置0
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// 第一行是否需要都置0
if (row0) {
for (int i = 0; i < col; i++) {
matrix[0][i] = 0;
}
}
// 第一列是否需要都置0
if (col0) {
for (int i = 0; i < row; i++) {
matrix[i][0] = 0;
}
}
}
}
終于通過(guò)了，執(zhí)行用時(shí)：2ms，內(nèi)存消耗：43.5MB。那么是否可以繼續(xù)優(yōu)化呢？
利用矩陣本身 優(yōu)化
首先，需要第一行和第一列都判斷一遍的嗎？可以只判斷其中一個(gè)即可，比如只判斷第一列是否需要置零，那么第一行是否需要置零就可以依賴matrix[0][0]了。在置零的時(shí)候，也是將第一列單獨(dú)判斷即可。
需要注意的是，置零操作需要從后往前，因?yàn)?code>matrix[0][0]會(huì)有雙重含義，所以最后判斷即可。來(lái)看看代碼：
class Solution {
public void setZeroes(int[][] matrix) {
// 第一列是否需要置零
boolean col0 = false;
int row = matrix.length;
int col = matrix[0].length;
// 判斷是否需要置零
for (int i = 0; i < row; i++) {
// 如果第一列不需要置零，并且第一列有數(shù)字是0，則col0設(shè)置為true
if (!col0 && matrix[i][0] == 0) {
col0 = true;
}
for (int j = 1; j < col; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
// 置零，從后往前開始，因?yàn)槿绻麖那巴?，第一行如果因?yàn)榈谝涣兄脼?，會(huì)對(duì)之后結(jié)果誤導(dǎo)
for (int i = row - 1; i >= 0; i--) {
// 第一列不動(dòng)
for (int j = col - 1; j >= 1; j--) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
// 第一列置零
if (col0) {
matrix[i][0] = 0;
}
}
}
}
總結(jié)
以上就是這道題目我的解答過(guò)程了，不知道大家是否理解了。我準(zhǔn)備把我刷力扣的過(guò)程記錄下來(lái)，作為這個(gè)系列的內(nèi)容，希望能和大家多多分享。
有興趣的話可以訪問我的博客或者關(guān)注我的公眾號(hào)、頭條號(hào)，說(shuō)不定會(huì)有意外的驚喜。
公眾號(hào)：健程之道
