这道题我感觉还是挺简单的,一下子就想到了,不过我的算法很简单很垃圾,效率很低,我一看完题的想法就是直接遍历一遍数组,然后把为0的元素的行和列都存起来,然后把这些行和列都置零就好了,但是这里会有重复,所以用HashSet来存就好了,然后就写出来了,以下是我的代码:
- class Solution {
- public void setZeroes(int[][] matrix) {
- int r = matrix.length;
- int c = matrix[0].length;
- Set
row = new HashSet(); - Set
column = new HashSet(); - for(int i =0;i
- for(int j=0;j
- if(matrix[i][j] == 0){
- row.add(i);
- column.add(j);
- }
- }
- }
-
- for(Integer i : row){
- matrix[i] = new int[c];
- }
-
- for(Integer j : column){
- for(int i =0;i
- matrix[i][j]=0;
- }
- }
- }
- }
看看题解,题解的第一种方法和我的差不多,但是他的感觉更容易理解,它没有拿两个set去记录要置零的行和列,而是拿两个boolean数组来标记(row标记行,col标记列),先第一遍遍历数组,对于遍历到的元素X,如果它等于0,就把两个标记数组中它对应的行和列改为true;然后第二遍遍历数组,对于遍历到的元素X,如果他对应的行或者列在标记数组中是true,就把这个元素改为0,这样其实只要两遍完整的遍历数组就可以,以下是题解第一种解法的代码:
- class Solution {
- public void setZeroes(int[][] matrix) {
- int m = matrix.length, n = matrix[0].length;
- boolean[] row = new boolean[m];
- boolean[] col = new boolean[n];
- for (int i = 0; i < m; i++) {
- for (int j = 0; j < n; j++) {
- if (matrix[i][j] == 0) {
- row[i] = col[j] = true;
- }
- }
- }
- for (int i = 0; i < m; i++) {
- for (int j = 0; j < n; j++) {
- if (row[i] || col[j]) {
- matrix[i][j] = 0;
- }
- }
- }
- }
- }
-
题解的第二种解法就是不另外开辟两个数组来标记,而是拿数组的第一行和第一列来标记,但是这样的话第一行和第一列的数就改变了,所以他创建了两个boolean变量flagCol0和flagRow0来标记第一行中是否有0,先遍历第一行,如果存在一个0就把flagRow0改为true,同理然后遍历第一列,然后去遍历数组中剩下的其他元素,如果是0,就把第一行和第一列中对应坐标下的元素改为0,然后再重新遍历一遍除第一行第一列外的元素,如果这个元素的行和列在标记数组(第一行第一列)中是0,那就把这个元素改成0(和题解1一样,只是标记数组变了),最后再看第一行和第一列的那两个标记变量是不是true,如果是再把第一行和第一列改成0,就可以了。我看完还有一个小疑惑,在第一遍遍历中把第一行和第一列的元素改成了0,如果两个标记变量都是false你没把第一行而第一列中改了的元素改回去啊,但一下子就想通了,如果把第一行或第一列中的元素改成了0说明这个元素在有0的行或列,它本来就要变成0,所以是我想多了,以下是题解二代码:
- class Solution {
- public void setZeroes(int[][] matrix) {
- int m = matrix.length, n = matrix[0].length;
- boolean flagCol0 = false, flagRow0 = false;
- for (int i = 0; i < m; i++) {
- if (matrix[i][0] == 0) {
- flagCol0 = true;
- }
- }
- for (int j = 0; j < n; j++) {
- if (matrix[0][j] == 0) {
- flagRow0 = true;
- }
- }
- for (int i = 1; i < m; i++) {
- for (int j = 1; j < n; j++) {
- if (matrix[i][j] == 0) {
- matrix[i][0] = matrix[0][j] = 0;
- }
- }
- }
- for (int i = 1; i < m; i++) {
- for (int j = 1; j < n; j++) {
- if (matrix[i][0] == 0 || matrix[0][j] == 0) {
- matrix[i][j] = 0;
- }
- }
- }
- if (flagCol0) {
- for (int i = 0; i < m; i++) {
- matrix[i][0] = 0;
- }
- }
- if (flagRow0) {
- for (int j = 0; j < n; j++) {
- matrix[0][j] = 0;
- }
- }
- }
- }
-
-
相关阅读:
近源渗透简介
大型项目中 MSAA 的方案参考
亮度问题还是动态问题确认
vite的搭建与使用
git撤回本地的commit或者push到远程的代码
22年多校第三场(F的证明
istio系列教程
【Windows Docker:安装nginx】
详解c++---map和set的封装
涨1100w播放,150w粉!B站UP主仅入站百天竟成功出圈!
-
原文地址:https://blog.csdn.net/qq_61009660/article/details/132699183