最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

经典面试题32_零矩阵解法思路

XAMPP相关 admin 528浏览 0评论

来源:LeetCode

难度:中等

描述:

编写一种算法,若M × N矩阵中某个元素为0,则将其所在的行与列清零。

示例1:

输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]

示例2:

输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

分析:

本题主要考察的是对二维数组的熟悉程度以及编码的扎实程度。题意不难理解,就是当二维数组中某个元素为0时,将其所在的列和行都置为0即可。

唯一需要注意的是咱们最好不要在遍历的过程中改变数组元素,否则处理起来比较麻烦,需要额外使用一个二维数组保存每个位子原来是否为0,并且徒增许多判断,容易带来理解成本和编码难度。在面试中最好采用简单、容易理解的方式去解题。

 

解题

方法一:数组标记法

思路:

采用两个标记数组,分别记录每一行和每一列是否有零出现。

首先对二维数组进行遍历,如果某个元素为 0,那么就将该元素所在的行和列所对应标记数组的位置置为true。

最后我们再次遍历该数组,用标记数组更新原数组即可。

 

代码:

 1public void setZeroes(int[][] matrix) {
 2    int m = matrix.length;
 3    int n = matrix[0].length;
 4    //两个数组、分别记录0元素所在的行和列
 5    boolean[] row = new boolean[m];
 6    boolean[] col = new boolean[n];
 7    for (int i = 0; i < m; i++) {
 8        for (int j = 0; j < n; j++) {
 9            if (matrix[i][j] == 0) {
10                //将0元素所在的行和列置为true
11                row[i] = col[j] = true;
12            }
13        }
14    }
15    //再次遍历二维数组,将元素置为0
16    for (int i = 0; i < m; i++) {
17        for (int j = 0; j < n; j++) {
18            //将0元素所在的行和列的所有元素置为0
19            if (row[i] || col[j]) {
20                matrix[i][j] = 0;
21            }
22        }
23    }
24}

时间复杂度:O(m*n) m和n分别为二维数组的行和列

空间复杂度:O(m + n)

 

以上仅是个人思路解法

转载请注明:XAMPP中文组官网 » 经典面试题32_零矩阵解法思路

您必须 登录 才能发表评论!