当前位置：首页 > news >正文

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

news 来源：原创 2024/9/15 17:40:27

一、题目描述
示例1：
在这里插入图片描述
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例2：
在这里插入图片描述
输入：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，并且要求使用原地算法，即不能使用额外的矩阵空间来存储中间结果。
挑战分析：
- 不能使用过多的额外空间，需要在原矩阵上进行操作。
- 需要准确地记录哪些行和列需要被置为 0，同时避免重复置零或错误置零的情况。

三、算法思路

标记法：
- 遍历整个矩阵，当遇到一个元素为 0 时，记录下其所在的行索引和列索引。可以使用两个集合（在 Go 语言中可以使用 map 类型来模拟集合）分别记录需要置零的行和列。
- 再次遍历矩阵，对于每一个元素，如果其所在的行索引或列索引在记录的需要置零的行或列集合中，将该元素置为 0。
巧用首行首列标记：
- 利用矩阵的首行和首列来标记哪些行和列需要被置为 0。
- 首先遍历矩阵的第一行和第一列，检查是否存在 0 元素。如果存在，分别设置两个标记变量，表示第一行和第一列是否需要被置为 0。
- 然后遍历矩阵的剩余部分（除了第一行和第一列），如果遇到一个元素为 0，则将其对应的第一行和第一列的元素置为 0。
- 最后根据首行和首列的标记以及第一行和第一列中被置为 0 的元素，将相应的行和列置为 0。需要注意的是，在处理第一行和第一列时，需要单独处理，因为它们被用来标记其他行和列。

四、Golang 实现及注释

标记法实现：

package mainfunc setZeroes(matrix [][]int) {rows := make(map[int]bool)cols := make(map[int]bool)m := len(matrix)n := len(matrix[0])// 遍历矩阵，记录需要置零的行和列for i := 0; i < m; i++ {for j := 0; j < n; j++ {if matrix[i][j] == 0 {rows[i] = truecols[j] = true}}}// 根据记录的行和列，将相应的元素置为零for i := 0; i < m; i++ {for j := 0; j < n; j++ {if rows[i] || cols[j] {matrix[i][j] = 0}}}
}

巧用首行首列标记实现：

package mainfunc setZeroes(matrix [][]int) {m := len(matrix)n := len(matrix[0])firstRowHasZero := falsefirstColHasZero := false// 检查第一行是否有零for j := 0; j < n; j++ {if matrix[0][j] == 0 {firstRowHasZero = truebreak}}// 检查第一列是否有零for i := 0; i < m; i++ {if matrix[i][0] == 0 {firstColHasZero = truebreak}}// 使用第一行和第一列来标记其他行和列是否需要置零for i := 1; i < m; i++ {for j := 1; j < n; j++ {if matrix[i][j] == 0 {matrix[i][0] = 0matrix[0][j] = 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 firstRowHasZero {for j := 0; j < n; j++ {matrix[0][j] = 0}}// 如果第一列需要置零if firstColHasZero {for i := 0; i < m; i++ {matrix[i][0] = 0}}
}

五、算法性能分析

标记法性能分析：
- 时间复杂度：需要两次遍历矩阵，每次遍历的时间复杂度为 $O (mn)$ ，所以总的时间复杂度为 $O (2 mn) = O (mn)$ 。
- 空间复杂度：使用了两个额外的集合来记录需要置零的行和列，空间复杂度为 $O (m + n)$ ，其中 m 是矩阵的行数，n 是矩阵的列数。
巧用首行首列标记性能分析：
- 时间复杂度：同样需要两次遍历矩阵，时间复杂度为 $O (mn)$ 。
- 空间复杂度：没有使用额外的空间来记录行和列的信息，只使用了两个标记变量，空间复杂度为 $O (1)$ 。

六、测试代码

标记法测试代码：

package mainimport ("reflect""testing"
)func TestSetZeroesMarking(t *testing.T) {tests := []struct {input    [][]intexpected [][]int}{{input:    [][]int{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}},expected: [][]int{{1, 0, 1}, {0, 0, 0}, {1, 0, 1}},},{input:    [][]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 _, test := range tests {originalInput := make([][]int, len(test.input))for i, row := range test.input {originalInput[i] = make([]int, len(row))copy(originalInput[i], row)}setZeroes(test.input)if!reflect.DeepEqual(test.input, test.expected) {t.Errorf("For input %v, expected %v but got %v", originalInput, test.expected, test.input)}}
}

巧用首行首列标记测试代码：

package mainimport ("reflect""testing"
)func TestSetZeroesFirstRowColMarking(t *testing.T) {tests := []struct {input    [][]intexpected [][]int}{{input:    [][]int{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}},expected: [][]int{{1, 0, 1}, {0, 0, 0}, {1, 0, 1}},},{input:    [][]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 _, test := range tests {originalInput := make([][]int, len(test.input))for i, row := range test.input {originalInput[i] = make([]int, len(row))copy(originalInput[i], row)}setZeroes(test.input)if!reflect.DeepEqual(test.input, test.expected) {t.Errorf("For input %v, expected %v but got %v", originalInput, test.expected, test.input)}}
}

七、总结与拓展

总结：
- 本题通过不同的方法实现了矩阵置零的功能，展示了在解决问题时可以根据问题的特点选择合适的算法。标记法是一种直观的方法，但需要额外的空间。巧用首行首列标记的方法则充分利用了矩阵本身的结构，实现了原地置零，并且只使用了常量空间。
- 在实际编程中，需要根据问题的具体要求和限制来选择最优的解决方案。对于空间复杂度要求较高的问题，可以考虑使用类似巧用首行首列标记的方法，充分挖掘问题的特性，以达到更好的性能。
拓展：
- 可以进一步思考如果矩阵中存在多个 0 元素，如何更高效地进行置零操作。
- 如果矩阵是稀疏矩阵（即大部分元素为 0），可以考虑使用特殊的数据结构来存储矩阵，以减少空间和时间的消耗。
- 本题的思路也可以应用到其他类似的问题中，例如在图像处理中，当一个像素点的颜色值为特定值时，需要将其周围的像素点也进行特定的处理。