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

一、题目描述
示例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) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

二、问题分析

1. 核心任务：给定一个矩阵，当遇到一个元素为 0 时，需要将其所在的行和列的所有元素都置为 0，并且要求使用原地算法，即不能使用额外的矩阵空间来存储中间结果。

2. 挑战分析：

   • 不能使用过多的额外空间，需要在原矩阵上进行操作。
   • 需要准确地记录哪些行和列需要被置为 0，同时避免重复置零或错误置零的情况。

三、算法思路

1. 标记法：

   • 遍历整个矩阵，当遇到一个元素为 0 时，记录下其所在的行索引和列索引。可以使用两个集合（在 Go 语言中可以使用 map 类型来模拟集合）分别记录需要置零的行和列。
   • 再次遍历矩阵，对于每一个元素，如果其所在的行索引或列索引在记录的需要置零的行或列集合中，将该元素置为 0。

2. 巧用首行首列标记：

   • 利用矩阵的首行和首列来标记哪些行和列需要被置为 0。
   • 首先遍历矩阵的第一行和第一列，检查是否存在 0 元素。如果存在，分别设置两个标记变量，表示第一行和第一列是否需要被置为 0。
   • 然后遍历矩阵的剩余部分（除了第一行和第一列），如果遇到一个元素为 0，则将其对应的第一行和第一列的元素置为 0。
   • 最后根据首行和首列的标记以及第一行和第一列中被置为 0 的元素，将相应的行和列置为 0。需要注意的是，在处理第一行和第一列时，需要单独处理，因为它们被用来标记其他行和列。

四、Golang 实现及注释

1. 标记法实现：

package main

func 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] = 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
			}
		}
	}
}

2. 巧用首行首列标记实现：

package main

func setZeroes(matrix [][]int) {
	m := len(matrix)
	n := len(matrix[0])
	firstRowHasZero := false
	firstColHasZero := false

	// 检查第一行是否有零
	for j := 0; j < n; j++ {
		if matrix[0][j] == 0 {
			firstRowHasZero = true
			break
		}
	}

	// 检查第一列是否有零
	for i := 0; i < m; i++ {
		if matrix[i][0] == 0 {
			firstColHasZero = 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
			}
		}
	}

	// 根据标记置零其他行和列
	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
		}
	}
}

五、算法性能分析

1. 标记法性能分析：

   • 时间复杂度：需要两次遍历矩阵，每次遍历的时间复杂度为 $O(mn)$，所以总的时间复杂度为 $O(2mn)=O(mn)$。
   • 空间复杂度：使用了两个额外的集合来记录需要置零的行和列，空间复杂度为 $O(m+n)$，其中 m 是矩阵的行数，n 是矩阵的列数。

2. 巧用首行首列标记性能分析：

   • 时间复杂度：同样需要两次遍历矩阵，时间复杂度为 $O(mn)$。
   • 空间复杂度：没有使用额外的空间来记录行和列的信息，只使用了两个标记变量，空间复杂度为 $O(1)$。

六、测试代码

1. 标记法测试代码：

package main

import (
	"reflect"
	"testing"
)

func TestSetZeroesMarking(t *testing.T) {
	tests := []struct {
		input    [][]int
		expected [][]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)
		}
	}
}

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

package main

import (
	"reflect"
	"testing"
)

func TestSetZeroesFirstRowColMarking(t *testing.T) {
	tests := []struct {
		input    [][]int
		expected [][]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)
		}
	}
}

七、总结与拓展

1. 总结：

   • 本题通过不同的方法实现了矩阵置零的功能，展示了在解决问题时可以根据问题的特点选择合适的算法。标记法是一种直观的方法，但需要额外的空间。巧用首行首列标记的方法则充分利用了矩阵本身的结构，实现了原地置零，并且只使用了常量空间。
   • 在实际编程中，需要根据问题的具体要求和限制来选择最优的解决方案。对于空间复杂度要求较高的问题，可以考虑使用类似巧用首行首列标记的方法，充分挖掘问题的特性，以达到更好的性能。

2. 拓展：

   • 可以进一步思考如果矩阵中存在多个 0 元素，如何更高效地进行置零操作。
   • 如果矩阵是稀疏矩阵（即大部分元素为 0），可以考虑使用特殊的数据结构来存储矩阵，以减少空间和时间的消耗。
   • 本题的思路也可以应用到其他类似的问题中，例如在图像处理中，当一个像素点的颜色值为特定值时，需要将其周围的像素点也进行特定的处理。

通过对“矩阵置零”问题的深入分析和解决，我们可以更好地理解原地算法和空间复杂度的优化方法。希望本文对大家理解和解决这个问题有所帮助。