矩阵是各种计算机科学、数学和工程领域中使用的基本数据结构。在某些情况下，我们可能需要根据特定条件或要求将某些矩阵元素设置为零。在本教程中，我们将讨论在 Java 中有效完成此任务的各种方法。
理解问题
给定一个矩阵，我们的目标是将矩阵中每个零元素的整行和整列设置为零。此操作有效地将包含至少一个零元素的行和列“清零”。
例如，考虑以下矩阵：
[1, 2, 3]
[4, 0, 6]
[7, 8, 9]
|
应用变换后，矩阵变为：[1, 0, 3]
[0, 0, 0]
[7, 0, 9]
|
简单的解决方案
获得所需结果的常用策略是利用简单的问题解决方法，通常不强调优化或效率考虑。它通常是解决问题最明显的方法，但在性能或资源使用方面可能不是最有效或最高效的。
为了使用简单的方法解决我们的问题，我们可以首先复制输入矩阵以保留原始值，然后遍历它以检测零元素。
当遇到零元素时，我们将复制矩阵中的整个相应行和列清零。最后，我们用从副本获得的修改值更新原始矩阵：
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);
}
|
时间优化方法
该方法的重点是通过使用额外的空间来存储矩阵中零元素的索引来提高解决方案的时间复杂度。
它首先遍历矩阵来识别零个元素，并将它们的行索引和列索引存储在单独的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);
}
|
最佳方法
这种方法通过在不使用额外空间的情况下修改原始矩阵来优化空间复杂度。
它利用矩阵的第一行和第一列来存储有关零个元素的信息。该算法首先检查第一行和第一列是否包含任何零。
然后，它通过将相应元素设置为零来标记第一行和第一列中的零元素。接下来，它遍历矩阵（不包括第一行和第一列）以标记第一行和第一列中的零个元素。
最后，如果需要，它会遍历第一行和第一列，将整个行或列更新为零。
我们将把上述步骤分解为单独的辅助方法。下面的代码检查矩阵的第一行中是否至少有一个零：
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);
}
|
结论
在本教程中，我们探索了将矩阵中的元素设置为零的各种方法。天真的方法旨在实现所需的结果，而不优先考虑优化或性能。相反，时间优化方法通过利用额外的空间来降低时间复杂度。
然而，最佳方法既提高了时间复杂度，又不需要任何额外的空间，使其成为上述所有方法中更好的选择。重要的是要承认这个问题可能还有其他几种最佳解决方案。