题目描述
给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用原地算法。
输入:matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出:[[1,0,1],[0,0,0],[1,0,1]] 输入: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]]
python完整代码
class Solution:
def setZeroes(self, matrix):
rows = len(matrix) # 获取矩阵的行数
cols = len(matrix[0]) # 获取矩阵的列数
# 定义两个集合用于存储应该置零的行号和列号
zero_rows = set()
zero_cols = set()
# 遍历整个矩阵,记录0元素所在的行和列
for i in range(rows):
for j in range(cols):
if matrix[i][j] == 0:
zero_rows.add(i)
zero_cols.add(j)
# 将需要置零的行和列的元素置为0
for i in range(rows):
for j in range(cols):
if i in zero_rows or j in zero_cols: # 如果i和j在元素0所在的行或列
matrix[i][j] = 0
if __name__ == "__main__":
solution = Solution()
# 测试用例1:矩阵中有0元素
matrix1 = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
print("原始矩阵1:")
for row in matrix1:
print(row)
solution.setZeroes(matrix1)
print("\n置零后的矩阵1:")
for row in matrix1:
print(row)
# 测试用例2:矩阵中没有0元素
matrix2 = [
[0, 1, 2, 0],
[3, 4, 5, 2],
[1, 3, 1, 5]
]
print("\n原始矩阵2:")
for row in matrix2:
print(row)
solution.setZeroes(matrix2)
print("\n置零后的矩阵2:")
for row in matrix2:
print(row)
# 测试用例3:矩阵中全是0元素
matrix3 = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0]
]
print("\n原始矩阵3:")
for row in matrix3:
print(row)
solution.setZeroes(matrix3)
print("\n置零后的矩阵3:")
for row in matrix3:
print(row)
class Solution:
def setZeroes(self, matrix):
rows = len(matrix) # 获取矩阵的行数
cols = len(matrix[0]) # 获取矩阵的列数
# 定义两个标志位,用于标记第一行和第一列是否需要置零
first_row_zero = False
first_col_zero = False
# 检查第一行是否有0元素
for j in range(cols):
if matrix[0][j] == 0:
first_row_zero = True
break
# 检查第一列是否有0元素
for i in range(rows):
if matrix[i][0] == 0:
first_col_zero = True
break
# 遍历除第一行和第一列以外的元素,若为0,则将对应的第一行和第一列置为0
for i in range(1, rows):
for j in range(1, cols):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# 根据第一行和第一列的标志位,将对应的行和列置为0
for i in range(1, rows):
for j in range(1, cols):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# 如果第一行需要置零,则将第一行置零
if first_row_zero:
for j in range(cols):
matrix[0][j] = 0
# 如果第一列需要置零,则将第一列置零
if first_col_zero:
for i in range(rows):
matrix[i][0] = 0
if __name__ == "__main__":
solution = Solution()
# 测试用例1:矩阵中有0元素
matrix1 = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
print("原始矩阵1:")
for row in matrix1:
print(row)
solution.setZeroes(matrix1)
print("\n置零后的矩阵1:")
for row in matrix1:
print(row)
# 测试用例2:矩阵中没有0元素
matrix2 = [
[0, 1, 2, 0],
[3, 4, 5, 2],
[1, 3, 1, 5]
]
print("\n原始矩阵2:")
for row in matrix2:
print(row)
solution.setZeroes(matrix2)
print("\n置零后的矩阵2:")
for row in matrix2:
print(row)
# 测试用例3:矩阵中全是0元素
matrix3 = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0]
]
print("\n原始矩阵3:")
for row in matrix3:
print(row)
solution.setZeroes(matrix3)
print("\n置零后的矩阵3:")
for row in matrix3:
print(row)
c++完整代码
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int rows = matrix.size(); // 获取矩阵的行数
int cols = matrix[0].size(); // 获取矩阵的列数
// 定义两个集合用于存储应该置零的行号和列号
unordered_set<int> zero_rows;
unordered_set<int> zero_cols;
// 遍历整个矩阵,记录0元素所在的行和列
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (matrix[i][j] == 0) {
zero_rows.insert(i);
zero_cols.insert(j);
}
}
}
// 将需要置零的行和列的元素置为0
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (zero_rows.count(i) || zero_cols.count(j)) { // 如果i和j在元素0所在的行或列
matrix[i][j] = 0;
}
}
}
}
};
int main() {
Solution solution;
// 测试用例1:矩阵中有0元素
vector<vector<int>> matrix1 = {
{1, 1, 1},
{1, 0, 1},
{1, 1, 1}
};
cout << "matrix 1:" << endl;
for (auto& row : matrix1) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
solution.setZeroes(matrix1);
cout << "after matrix 1:" << endl;
for (auto& row : matrix1) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
vector<vector<int>> matrix2 = {
{0, 1, 2, 0},
{3, 4, 5, 2},
{1, 3, 1, 5}
};
cout << "matrix 2:" << endl;
for (auto& row : matrix2) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
solution.setZeroes(matrix2);
cout << "after matrix 2:" << endl;
for (auto& row : matrix2) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
vector<vector<int>> matrix3 = {
{0, 1, 0},
{1, 0, 1},
{0, 1, 0}
};
cout << "matrix 3:" << endl;
for (auto& row : matrix3) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
solution.setZeroes(matrix3);
cout << "after matrix 3:" << endl;
for (auto& row : matrix3) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int rows = matrix.size(); // 获取矩阵的行数
int cols = matrix[0].size(); // 获取矩阵的列数
// 定义两个标志位,用于标记第一行和第一列是否需要置零
bool first_row_zero = false;
bool first_col_zero = false;
// 检查第一行是否有0元素
for (int j = 0; j < cols; ++j) {
if (matrix[0][j] == 0) {
first_row_zero = true;
break;
}
}
// 检查第一列是否有0元素
for (int i = 0; i < rows; ++i) {
if (matrix[i][0] == 0) {
first_col_zero = true;
break;
}
}
// 遍历除第一行和第一列以外的元素,若为0,则将对应的第一行和第一列置为0
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;
}
}
}
// 根据第一行和第一列的标志位,将对应的行和列置为0
for (int i = 1; i < rows; ++i) {
for (int j = 1; j < cols; ++j) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// 如果第一行需要置零,则将第一行置零
if (first_row_zero) {
for (int j = 0; j < cols; ++j) {
matrix[0][j] = 0;
}
}
// 如果第一列需要置零,则将第一列置零
if (first_col_zero) {
for (int i = 0; i < rows; ++i) {
matrix[i][0] = 0;
}
}
}
};
int main() {
Solution solution;
// 测试用例
vector<vector<int>> matrix1 = {
{1, 1, 1},
{1, 0, 1},
{1, 1, 1}
};
cout << "matrix 1:" << endl;
for (auto& row : matrix1) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
solution.setZeroes(matrix1);
cout << "after matrix 1:" << endl;
for (auto& row : matrix1) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
vector<vector<int>> matrix2 = {
{0, 1, 2, 0},
{3, 4, 5, 2},
{1, 3, 1, 5}
};
cout << "matrix 2:" << endl;
for (auto& row : matrix2) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
solution.setZeroes(matrix2);
cout << "after matrix 2:" << endl;
for (auto& row : matrix2) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
vector<vector<int>> matrix3 = {
{0, 1, 0},
{1, 0, 1},
{0, 1, 0}
};
cout << "matrix 3:" << endl;
for (auto& row : matrix3) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
solution.setZeroes(matrix3);
cout << "after matrix 3:" << endl;
for (auto& row : matrix3) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
return 0;
}
Java完整代码
import java.util.HashSet;
import java.util.Set;
public class setZeroes {
public void setZeroes1(int[][] matrix) {
int rows = matrix.length; // 获取矩阵的行数
int cols = matrix[0].length; // 获取矩阵的列数
// 定义两个集合用于存储应该置零的行号和列号
Set<Integer> zeroRows = new HashSet<>();
Set<Integer> zeroCols = new HashSet<>();
// 遍历整个矩阵,记录0元素所在的行和列
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 0) {
zeroRows.add(i);
zeroCols.add(j);
}
}
}
// 将需要置零的行和列的元素置为0
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (zeroRows.contains(i) || zeroCols.contains(j)) { // 如果i和j在元素0所在的行或列
matrix[i][j] = 0;
}
}
}
}
public static void main(String[] args) {
setZeroes setZeroes1 = new setZeroes();
// 测试用例1:矩阵中有0元素
int[][] matrix1 = {
{1, 1, 1},
{1, 0, 1},
{1, 1, 1}
};
System.out.println("原始矩阵1:");
for (int[] row : matrix1) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
setZeroes1.setZeroes1(matrix1);
System.out.println("\n置零后的矩阵1:");
for (int[] row : matrix1) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
int[][] matrix2 = {
{0, 1, 2, 0},
{3, 4, 5, 2},
{1, 3, 1, 5}
};
System.out.println("原始矩阵2:");
for (int[] row : matrix2) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
setZeroes1.setZeroes1(matrix2);
System.out.println("\n置零后的矩阵2:");
for (int[] row : matrix2) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
int[][] matrix3 = {
{0, 1, 0},
{1, 0, 1},
{0, 1, 0}
};
System.out.println("原始矩阵3:");
for (int[] row : matrix3) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
setZeroes1.setZeroes1(matrix3);
System.out.println("\n置零后的矩阵3:");
for (int[] row : matrix3) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
}
}
import java.util.HashSet;
import java.util.Set;
public class setZeroes2 {
public void setZeroes(int[][] matrix) {
int rows = matrix.length; // 获取矩阵的行数
int cols = matrix[0].length; // 获取矩阵的列数
// 定义两个标志位,用于标记第一行和第一列是否需要置零
boolean firstRowZero = false;
boolean firstColZero = false;
// 检查第一行是否有0元素
for (int j = 0; j < cols; j++) {
if (matrix[0][j] == 0) {
firstRowZero = true;
break;
}
}
// 检查第一列是否有0元素
for (int i = 0; i < rows; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
// 遍历除第一行和第一列以外的元素,若为0,则将对应的第一行和第一列置为0
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;
}
}
}
// 根据第一行和第一列的标志位,将对应的行和列置为0
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// 如果第一行需要置零,则将第一行置零
if (firstRowZero) {
for (int j = 0; j < cols; j++) {
matrix[0][j] = 0;
}
}
// 如果第一列需要置零,则将第一列置零
if (firstColZero) {
for (int i = 0; i < rows; i++) {
matrix[i][0] = 0;
}
}
}
public static void main(String[] args) {
setZeroes2 setZeroes = new setZeroes2();
// 测试用例1:矩阵中有0元素
int[][] matrix1 = {
{1, 1, 1},
{1, 0, 1},
{1, 1, 1}
};
System.out.println("原始矩阵1:");
for (int[] row : matrix1) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
setZeroes.setZeroes(matrix1);
System.out.println("\n置零后的矩阵1:");
for (int[] row : matrix1) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
int[][] matrix2 = {
{0, 1, 2, 0},
{3, 4, 5, 2},
{1, 3, 1, 5}
};
System.out.println("原始矩阵2:");
for (int[] row : matrix2) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
setZeroes.setZeroes(matrix2);
System.out.println("\n置零后的矩阵2:");
for (int[] row : matrix2) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
int[][] matrix3 = {
{0, 1, 0},
{1, 0, 1},
{0, 1, 0}
};
System.out.println("原始矩阵3:");
for (int[] row : matrix3) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
setZeroes.setZeroes(matrix3);
System.out.println("\n置零后的矩阵3:");
for (int[] row : matrix3) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
}
}