1. 概述
矩阵是计算机科学、数学和工程领域中基础的数据结构。在某些场景下，我们可能需要根据特定条件或需求将矩阵的某些元素设置为零。本教程将讨论如何在Java中高效地实现这一任务的各种方法。
2. 问题理解
给定一个矩阵，我们的目标是将矩阵中每个零元素所在的整行和整列设置为零。这个操作会有效地“清除”包含至少一个零元素的行和列。
例如，考虑以下矩阵：
[1, 2, 3]
[4, 0, 6]
[7, 8, 9]
经过变换后，矩阵变为：
[1, 0, 3]
[0, 0, 0]
[7, 0, 9]
3. 简单解决方案
一种常见的策略是使用简单的解决问题方法，通常不强调优化或效率。这通常是解决问题的最直观方式，但在性能和资源使用方面可能不是最有效或高效的。
要使用简单方法解决这个问题，我们可以首先复制输入矩阵以保留原始值，然后遍历它来检测零元素。
遇到零元素时，我们继续在复制的矩阵中将整个对应行和列设置为零。最后，我们用修改后的值更新原始矩阵：
public class SetMatrixToZero {
static void setZeroesByNaiveApproach(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
int [][] result = new int[row][col];
for (int i = 0; i<row; i++) {
for (int j = 0; j < col; j++) {
result[i][j] = matrix[i][j];
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 0) {
for (int k = 0; k < col; k++) {
result[i][k] = 0;
}
for (int k = 0; k < row; k++) {
result[k][j] = 0;
}
}
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
matrix[i][j] = result[i][j];
}
}
}
}
虽然这种方法直接明了，但其时间复杂度为O((mn)∗(m+n))，其中m是行数，n是列数。空间复杂度为O(m*n)。对于大型矩阵，这种方法可能效率不高。
让我们通过以下测试来验证这种方法：
@Test
void givenMatrix_whenUsingSetZeroesByNaiveApproach_thenSetZeroes() {
int[][] matrix = {
{1, 2, 3},
{4, 0, 6},
{7, 8, 9}
};
int[][] expected = {
{1, 0, 3},
{0, 0, 0},
{7, 0, 9}
};
SetMatrixToZero.setZeroesByNaiveApproach(matrix);
assertArrayEquals(expected, matrix);
}
4. 时间优化方法
这个方法专注于通过使用额外空间存储矩阵中零元素的索引来提高时间复杂度。
首先，它遍历矩阵来识别零元素，并将它们的行和列索引分别存储在单独的HashSet中。然后，再次遍历矩阵，根据存储的索引设置对应的行和列为零：
static void setZeroesByTimeOptimizedApproach(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
Set<Integer> rowSet = new HashSet<>();
Set<Integer> colSet = new HashSet<>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 0) {
rowSet.add(i);
colSet.add(j);
}
}
}
for (int row: rowSet) {
for (int j = 0; j < cols; j++) {
matrix[row][j] = 0;
}
}
for (int col: colSet) {
for (int i = 0; i < rows; i++) {
matrix[i][col] = 0;
}
}
}
这种方法的时间复杂度为O(m * n)，并需要额外的空间O(m + n)来存储索引，这对于大型矩阵来说可能不够高效。
我们可以通过以下测试验证上述方法：
@Test
void givenMatrix_whenUsingSetZeroesByTimeOptimizedApproach_thenSetZeroes() {
int[][] matrix = {
{1, 2, 3},
{4, 0, 6},
{7, 8, 9}
};
int[][] expected = {
{1, 0, 3},
{0, 0, 0},
{7, 0, 9}
};
SetMatrixToZero.setZeroesByTimeOptimizedApproach(matrix);
assertArrayEquals(expected, matrix);
}
5. 最优方法
这种方法通过修改原矩阵而无需额外空间，优化了空间复杂度。
它利用矩阵的第一行和第一列来存储零元素的信息。算法首先检查第一行和第一列是否包含任何零。
然后，它标记第一行和第一列中的零元素，将相应的元素设为零。接下来，它遍历矩阵（排除第一行和第一列）来标记第一行和第一列中的零元素。
最后，它遍历第一行和第一列，如果需要，更新整个行或列为零。
我们将上述步骤分解成单独的辅助方法。以下是检查矩阵的第一行是否有至少一个零的方法：
static boolean hasZeroInFirstRow(int[][] matrix, int cols) {
for (int j = 0; j < cols; j++) {
if (matrix[0][j] == 0) {
return true;
}
}
return false;
}
类似地，我们检查矩阵的第一列是否有至少一个零：
static boolean hasZeroInFirstCol(int[][] matrix, int rows) {
for (int i = 0; i < rows; i++) {
if (matrix[i][0] == 0) {
return true;
}
}
return false;
}
我们通过设置第一行和第一列中对应位置的元素为零来标记矩阵中的零位置：
static void markZeroesInMatrix(int[][] matrix, int rows, int cols) {
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
}
接下来，根据第一列的标记设置行的零：
static void setZeroesInRows(int[][] matrix, int rows, int cols) {
for (int i = 1; i < rows; i++) {
if (matrix[i][0] == 0) {
for (int j = 1; j < cols; j++) {
matrix[i][j] = 0;
}
}
}
}
同样，根据第一行的标记设置列的零：
static void setZeroesInCols(int[][] matrix, int rows, int cols) {
for (int j = 1; j < cols; j++) {
if (matrix[0][j] == 0) {
for (int i = 1; i < rows; i++) {
matrix[i][j] = 0;
}
}
}
}
现在，我们将第一行的所有元素设置为零：
static void setZeroesInFirstRow(int[][] matrix, int cols) {
for (int j = 0; j < cols; j++) {
matrix[0][j] = 0;
}
}
我们对第一列采用类似的方法：
static void setZeroesInFirstCol(int[][] matrix, int rows) {
for (int i = 0; i < rows; i++) {
matrix[i][0] = 0;
}
}
我们将所有前面的步骤合并到以下方法中执行：
static void setZeroesByOptimalApproach(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
boolean firstRowZero = hasZeroInFirstRow(matrix, cols);
boolean firstColZero = hasZeroInFirstCol(matrix, rows);
markZeroesInMatrix(matrix, rows, cols);
setZeroesInRows(matrix, rows, cols);
setZeroesInCols(matrix, rows, cols);
if (firstRowZero) {
setZeroesInFirstRow(matrix, cols);
}
if (firstColZero) {
setZeroesInFirstCol(matrix, rows);
}
}
这种方法消除了额外空间的需求，空间复杂度进一步降低到O(1)。总体空间复杂度仍为O(m * n)。
它在现有矩阵内完成目标，保持时间复杂度为O(m * n)，其中n代表行数，n表示列数。这种效率使其适合处理大型矩阵。
让我们编写测试来评估这种方法：
@Test
void givenMatrix_whenUsingSetZeroesByOptimalApproach_thenSetZeroes() {
int[][] matrix = {
{1, 2, 3},
{4, 0, 6},
{7, 8, 9}
};
int[][] expected = {
{1, 0, 3},
{0, 0, 0},
{7, 0, 9}
};
SetMatrixToZero.setZeroesByOptimalApproach(matrix);
assertArrayEquals(expected, matrix);
}
6. 总结
在这篇教程中，我们探讨了在矩阵中设置元素为零的不同方法。简单方法旨在达到目标，而不强调优化或性能。相比之下，时间优化方法通过使用额外空间降低了时间复杂度。
然而，最优方法同时优化了时间和空间复杂度，不需要额外空间，因此在上述所有方法中更胜一筹。重要的是，这个问题可能还有其他多种最优解决方案。
如常，完整的源代码可在GitHub上找到。