leetcode73：矩阵置零

题目链接

leetcode

题目描述

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。
请使用 原地 算法。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

/*
    使用标记数组

    时间复杂度：O(mn)
        其中 m 是矩阵的行数，n 是矩阵的列数。
        需要遍历矩阵两次。
    空间复杂度：O(m + n)
        需要分别记录每一行或每一列是否有 0。
*/
class Solution_0 {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int m = matrix.size(), n = matrix[0].size();

        vector<int> row(m), col(n);
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (!matrix[i][j]) row[i] = col[j] = 1;
            }
        }
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (row[i] || col[j]) matrix[i][j] = 0;
            }
        }
    }
};

/*
    使用两个标记变量

    预处理出两个标记变量，
    使用其他行与列去处理第一行与第一列，
    使用第一行与第一列去更新其他行与列，
    最后使用两个标记变量更新第一行与第一列。

    时间复杂度：O(mn)
        其中 m 是矩阵的行数，n 是矩阵的列数。
        至多只需要遍历该矩阵两次。
    空间复杂度：O(1)
        使用两个变量，记录第一行和第一列是否有 0。
*/
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int m = matrix.size(), n = matrix[0].size();

        int row = 1, col = 1;
        for (int i = 0; i < m; i ++) if (!matrix[i][0]) col = 0;
        for (int i = 0; i < n; i ++) if (!matrix[0][i]) row = 0;
        
        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;
                }
            }
        }
        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;
                }
            }
        }

        if (!col) for (int i = 0; i < m; i ++) matrix[i][0] = 0;
        if (!row) for (int i = 0; i < n; i ++) matrix[0][i] = 0;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> matrix = {
        {0, 1, 2, 0},
        {3, 4, 5, 2},
        {1, 3, 1, 5}
    };
    solution.setZeroes(matrix);

    cout << "Modified matrix: " << endl;
    for (const auto& row : matrix) {
        for (int num : row) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

// deepCopyMatrix 深拷贝二维矩阵
func deepCopyMatrix(matrix [][]int) [][]int {
	if len(matrix) == 0 {
		return nil
	}
	m := len(matrix)
	n := len(matrix[0])
	copied := make([][]int, m)
	for i := 0; i < m; i++ {
		copied[i] = make([]int, n)
		copy(copied[i], matrix[i])
	}
	return copied
}

/*
    1.创建两个标记数组 rows 和 cols，分别用于标记需要置零的行和列。
    2.遍历矩阵。若遇到元素为 0，则将其所在的行和列在标记数组中标记为零。
    3.再次遍历矩阵，将标记为零的行和列的元素置为 0。

    时间复杂度：O(mn)
        其中 m 和 n 分别为矩阵的行数和列数，需要遍历两次矩阵。
    空间复杂度：O(m+n)
        使用了两个标记数组 rows 和 cols，其长度分别为矩阵的行数和列数。
*/
func setZeroes_0(matrix [][]int)  {
    m, n := len(matrix), len(matrix[0])
    // 使用两个标记数组，记录哪些行和列需要置零
    rows := make([]bool, m)
    cols := make([]bool, n)
    // 遍历矩阵，标记需要置零的行和列
    for i := 0; i < m; i ++ {
        for j := 0; j < n; j ++ {
            if matrix[i][j] == 0 {
                rows[i] = true
                cols[j] = true
            }
        }
    }
    // 遍历矩阵，将需要置零的行和列置零
    for i := 0; i < m; i ++ {
        for j := 0; j < n; j ++ {
            if rows[i] || cols[j] {
                matrix[i][j] = 0
            }
        } 
    }
}

/*
    1.标记第一行和第一列是否需要置零。
    2.使用第一行和第一列来标记需要置零的行和列。
        遍历矩阵的其余部分。
        若某个元素为 0，则将其所在的行的第一个元素和列的第一个元素标记为 0。
    3.再次遍历矩阵的其余部分，将标记为 0 的行和列的元素置为 0。
    4.若第一行或第一列有 0，则将第一行或第一列全部置为 0。

    时间复杂度：O(mn)
        其中 m 和 n 分别为矩阵的行数和列数，需要遍历两次矩阵。
    空间复杂度：O(1)
        使用两个变量，记录第一行和第一列是否有 0。
*/
func setZeroes(matrix [][]int)  {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
		return
	}

    m, n := len(matrix), len(matrix[0])
    // 使用两个变量，标记第一行和第一列是否需要置零
    row, col := false, false
    
    // 检查第一行是否有元素为零
    for j := 0; j < n; j ++ {
        if matrix[0][j] == 0 {
            row = true
            break
        }
    }
    // 检查第一列是否有元素为零
    for i := 0; i < m; i ++ {
        if matrix[i][0] == 0 {
            col = true
            break
        }
    }

    // 使用第一行和第一列，标记需要置零的行和列
    for i := 1; i < m; i ++ {
        for j := 1; j < n; j ++ {
            if matrix[i][j] == 0 {
                matrix[i][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
            }
        }
    }

    // 若第一行需要置零，则将第一行全部置零
    if row {
        for j := 0; j < n; j ++ {
            matrix[0][j] = 0
        }
    }
    // 若第一列需要置零，则将第一列全部置零
    if col {
        for i := 0; i < m; i ++ {
            matrix[i][0] = 0
        }
    }
}

func main() {
    // 测试用例
    testCases := []struct {
        matrix   [][]int
        expected [][]int
    }{
        {
            matrix: [][]int{
                {1,1,1},
                {1,0,1},
                {1,1,1},
            },
            expected: [][]int{
                {1,0,1},
                {0,0,0},
                {1,0,1},
            },
        },
        {
            matrix: [][]int{
                {0,1,2,0},
                {3,4,5,2},
                {1,3,1,5},
            },
            expected: [][]int{
                {0,0,0,0},
                {0,4,5,0},
                {0,3,1,0},
            },
        },
    }

    for i, tc := range testCases {
        fmt.Printf("Test Case %d, Input: matrix = %v\n", i+1, tc.matrix)
        setZeroes(tc.matrix)
        resultStr := fmt.Sprintf("%v", tc.matrix)
        expectedStr := fmt.Sprintf("%v", tc.expected)
        
        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
	}
}