力扣最热一百题——矩阵置零
目录
题目链接：73. 矩阵置零 - 力扣（LeetCode）
题目描述
示例
提示：
解法一：采用标记数组遍历处理
Java写法：
C++写法：
优化
解法二：优化解法之标记变量
Java写法：
总结
题目链接：73. 矩阵置零 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述
给定一个 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.lengthn == matrix[0].length1 <= m, n <= 200-<= matrix[i][j] <=
解法一：采用标记数组遍历处理
-
标记零的位置：首先遍历整个矩阵，找到所有为0的元素，并在辅助的标记数组中记录这些位置。这一步的作用是确保后续的置零操作不会影响还未检查到的位置。
-
执行置零操作：在标记完成后，再次遍历矩阵。对于标记数组中对应为0的位置，将原矩阵中该元素所在的整行和整列都置为0。
整个过程的时间复杂度是O(MN)，因为遍历了两次矩阵，而空间复杂度为O(MN)，由于使用了额外的标记数组。
Java写法：
class Solution {
public void setZeroes(int[][] matrix) {
// 获取纵向的长度
int lenY = matrix.length;
// 获取横向的长度
int lenX = matrix[0].length;
// 定义标记数组用于标记0的位置
int[][] isZero = new int[lenY][lenX];
// 给标记数组赋值，寻找全部的0的位置
for(int x=0;x < lenX; x++){
for(int y=0;y < lenY;y++){
if(matrix[y][x] == 0){
// 标记为0
isZero[y][x] = 1;
}
}
}
// 操作原数组，如果被标记数组标记为0的位置的xy方向全部置零
for(int x=0;x < lenX; x++){
for(int y=0;y < lenY;y++){
if(isZero[y][x] == 1){
setXYZero(matrix,y,x);
}
}
}
}
/**
* 1 2 3
* 4 0 6
* 7 8 9
* @param aimArr 置零方法，将x，y位置的横纵方向上的数全部置零
* @param y
* @param x
*/
public void setXYZero(int[][] aimArr,int y,int x){
for (int i = 0; i < aimArr[0].length; i++) {
aimArr[y][i] = 0;
}
for (int i = 0; i < aimArr.length; i++) {
aimArr[i][x] = 0;
}
}
}
C++写法：
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int lenY = matrix.size(); // 获取矩阵的行数
int lenX = matrix[0].size(); // 获取矩阵的列数
vector<vector<int>> isZero(lenY, vector<int>(lenX, 0)); // 定义标记数组
// 标记数组赋值，寻找0的位置
for(int x = 0; x < lenX; x++) {
for(int y = 0; y < lenY; y++) {
if(matrix[y][x] == 0) {
isZero[y][x] = 1; // 标记0
}
}
}
// 根据标记数组对矩阵进行置零操作
for(int x = 0; x < lenX; x++) {
for(int y = 0; y < lenY; y++) {
if(isZero[y][x] == 1) {
setXYZero(matrix, y, x); // 置零
}
}
}
}
// 将指定位置的行和列全部置零
void setXYZero(vector<vector<int>>& aimArr, int y, int x) {
for (int i = 0; i < aimArr[0].size(); i++) {
aimArr[y][i] = 0; // 置零行
}
for (int i = 0; i < aimArr.size(); i++) {
aimArr[i][x] = 0; // 置零列
}
}
};优化
但是我还看见了一种简化写法是官方给的我这里借着这个思路复写一下，大家可以去看官方题解。
class Solution {
public void setZeroes(int[][] matrix) {
int lenY = matrix.length;
int lenX = matrix[0].length;
// 使用第一行和第一列用于标记数组
boolean[] isZeroX = new boolean[lenX];
boolean[] isZeroY = new boolean[lenY];
// 遍历数组寻找0的位置
for(int i = 0; i < lenY; i++){
for(int j = 0; j < lenX; j++){
if(matrix[i][j] == 0){
// 找到了这个位置有0那么就设置标记数组
isZeroX[j] = true;
isZeroY[i] = true;
}
}
}
// 然后只要是发现位置上的行或列是包含0的那么就设置为0
for(int i = 0; i < lenY; i++){
for(int j = 0; j < lenX; j++){
if(isZeroX[j] || isZeroY[i]){
matrix[i][j] = 0;
}
}
}
}
}
解法二：优化解法之标记变量
如果优化，可以将空间复杂度降低到O(1)，利用矩阵本身的某一行和某一列作为标记区域。
优化后的算法不再使用额外的标记数组，而是通过矩阵的第一行和第一列来标记哪些行和列需要置零。具体优化步骤如下：
- 首先，检查矩阵的第一行和第一列是否有零，并记录下来。
- 然后，使用第一行和第一列作为标记区域，遍历其余部分矩阵，标记哪些行和列需要置零。
- 接着，根据第一行和第一列的标记信息，置零相应的行和列。
- 最后，检查第一行和第一列，必要时将它们置零。
Java写法：
class Solution {
public void setZeroes(int[][] matrix) {
// 获取矩阵的行列数
int lenY = matrix.length;
int lenX = matrix[0].length;
// 标记第一行和第一列是否需要置零
boolean firstRowZero = false;
boolean firstColZero = false;
// 检查第一列是否有零
for (int y = 0; y < lenY; y++) {
if (matrix[y][0] == 0) {
firstColZero = true;
break;
}
}
// 检查第一行是否有零
for (int x = 0; x < lenX; x++) {
if (matrix[0][x] == 0) {
firstRowZero = true;
break;
}
}
// 使用第一行和第一列作为标记
for (int y = 1; y < lenY; y++) {
for (int x = 1; x < lenX; x++) {
if (matrix[y][x] == 0) {
matrix[y][0] = 0;
matrix[0][x] = 0;
}
}
}
// 置零操作（除去第一行和第一列）
for (int y = 1; y < lenY; y++) {
for (int x = 1; x < lenX; x++) {
if (matrix[y][0] == 0 || matrix[0][x] == 0) {
matrix[y][x] = 0;
}
}
}
// 如果第一列需要置零
if (firstColZero) {
for (int y = 0; y < lenY; y++) {
matrix[y][0] = 0;
}
}
// 如果第一行需要置零
if (firstRowZero) {
for (int x = 0; x < lenX; x++) {
matrix[0][x] = 0;
}
}
}
}
果然由于少了一次赋值为零的遍历，速度直接就上来了，加上用的也不是二维数组了，现在的速度更快了。
总结
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈烦死了
