73. 矩陣置零：
給定一個 m x n 的矩陣，如果一個元素為 0 ，則將其所在行和列的所有元素都設(shè)為 0 。請使用 原地 算法。
樣例 1：
輸入：
matrix = [[1,1,1],[1,0,1],[1,1,1]]
輸出：
[[1,0,1],[0,0,0],[1,0,1]]
樣例 2：
文章來源：http://www.zghlxwxcb.cn/news/detail-672599.html
輸入：
matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
輸出：
[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
提示：
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -231 <= matrix[i][j] <= 231 - 1
進階：
- 一個直觀的解決方案是使用 O(mn) 的額外空間，但這并不是一個好的解決方案。
- 一個簡單的改進方案是使用 O(m + n) 的額外空間，但這仍然不是最好的解決方案。
- 你能想出一個僅使用常量空間的解決方案嗎？
分析：
- 面對這道算法題目，二當家的再次陷入了沉思。
- 要遍歷整個矩陣是肯定的了，所以時間復雜度上似乎沒什么大的技巧，重點在空間復雜度上。
- 不使用額外空間，直接在遍歷中就將行和列置0，會導致還沒有遍歷到的值丟失。
- 可以將原矩陣整體拷貝一份作為備份，然后遍歷這個備份的矩陣，去直接將原矩陣置0，這樣會使用 O(mn) 的額外空間。
- 一個簡單的改進方案是使用兩個額外的數(shù)組，存儲每一行是否出現(xiàn)過0，和每一列是否出現(xiàn)過0，然后再利用這兩個額外的標記數(shù)組將原矩陣置0，這樣會使用 O(m + n) 的額外空間。
- 可以進一步優(yōu)化，我們可以用矩陣的第一行和第一列代作為標記數(shù)組。但這樣會導致原數(shù)組的第一行和第一列被修改，無法記錄它們是否原本包含 0。因此我們需要額外使用兩個標記變量分別記錄第一行和第一列是否原本包含 0，這樣僅僅需要 O(1) 的額外空間。
題解：
rust：
impl Solution {
pub fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
let (m, n) = (matrix.len(), matrix[0].len());
let (mut flag_row0, mut flag_col0) = (false, false);
// 第一行是否有0
for i in 0..n {
if matrix[0][i] == 0 {
flag_row0 = true;
break;
}
}
// 第一列是否有0
for i in 0..m {
if matrix[i][0] == 0 {
flag_col0 = true;
break;
}
}
// 標記
(1..m).for_each(|i| {
(1..n).for_each(|j| {
if matrix[i][j] == 0 {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
});
});
// 置0
(1..m).for_each(|i| {
(1..n).for_each(|j| {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0;
}
});
});
// 第一行置0
if flag_row0 {
for i in 0..n {
matrix[0][i] = 0;
}
}
// 第一列置0
if flag_col0 {
for i in 0..m {
matrix[i][0] = 0;
}
}
}
}
go：
func setZeroes(matrix [][]int) {
m, n := len(matrix), len(matrix[0])
row0, col0 := false, false
// 第一行是否有0
for _, v := range matrix[0] {
if v == 0 {
row0 = true
break
}
}
// 第一列是否有0
for _, r := range matrix {
if r[0] == 0 {
col0 = true
break
}
}
// 標記
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if matrix[i][j] == 0 {
matrix[i][0] = 0
matrix[0][j] = 0
}
}
}
// 置0
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0
}
}
}
// 第一行置0
if row0 {
for i := 0; i < n; i++ {
matrix[0][i] = 0
}
}
// 第一列置0
if col0 {
for _, r := range matrix {
r[0] = 0
}
}
}
c++：
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
const int m = matrix.size(), n = matrix[0].size();
bool flag_row0 = false, flag_col0 = false;
// 第一行是否有0
for (int i = 0; i < n; ++i) {
if (!matrix[0][i]) {
flag_row0 = true;
break;
}
}
// 第一列是否有0
for (int i = 0; i < m; ++i) {
if (!matrix[i][0]) {
flag_col0 = true;
break;
}
}
// 標記
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (!matrix[i][j]) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
// 置0
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (!matrix[i][0] || !matrix[0][j]) {
matrix[i][j] = 0;
}
}
}
// 第一行置0
if (flag_row0) {
for (int i = 0; i < n; ++i) {
matrix[0][i] = 0;
}
}
// 第一列置0
if (flag_col0) {
for (int i = 0; i < m; ++i) {
matrix[i][0] = 0;
}
}
}
};
python：
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
m, n = len(matrix), len(matrix[0])
# 第一行是否有0
flag_row0 = any(matrix[0][i] == 0 for i in range(n))
# 第一列是否有0
flag_col0 = any(matrix[i][0] == 0 for i in range(m))
# 標記
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0
# 置0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# 第一行置0
if flag_row0:
for j in range(n):
matrix[0][j] = 0
# 第一列置0
if flag_col0:
for i in range(m):
matrix[i][0] = 0
java：
class Solution {
public void setZeroes(int[][] matrix) {
final int m = matrix.length, n = matrix[0].length;
boolean flagRow0 = false, flagCol0 = false;
// 第一行是否有0
for (int i = 0; i < m; ++i) {
if (matrix[i][0] == 0) {
flagCol0 = true;
break;
}
}
// 第一列是否有0
for (int i = 0; i < n; ++i) {
if (matrix[0][i] == 0) {
flagRow0 = true;
break;
}
}
// 標記
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
// 置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;
}
}
}
// 第一行置0
if (flagRow0) {
for (int i = 0; i < n; ++i) {
matrix[0][i] = 0;
}
}
// 第一列置0
if (flagCol0) {
for (int i = 0; i < m; ++i) {
matrix[i][0] = 0;
}
}
}
}
非常感謝你閱讀本文~
歡迎【點贊】【收藏】【評論】三連走一波~
放棄不難，但堅持一定很酷~
希望我們大家都能每天進步一點點~
本文由 二當家的白帽子：https://le-yi.blog.csdn.net/ 博客原創(chuàng)~文章來源地址http://www.zghlxwxcb.cn/news/detail-672599.html
到了這里，關(guān)于算法leetcode｜73. 矩陣置零（rust重拳出擊）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
