LeetCode 73 Set Matrix Zeroes(设矩阵元素为0)(Array)(*)

简介: 版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/52139263 翻译给定一个mm x nn的矩阵matrix,如果其中一个元素为0,那么将其所在的行和列的元素统统设为0。
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/52139263

翻译

给定一个m x n的矩阵matrix,如果其中一个元素为0,那么将其所在的行和列的元素统统设为0。要求就地计算。

跟进:

你使用了额外的空间吗?

一个直接的解决方案是使用O(mn)的空间,但这不是个好主意。
一个简单的改进是使用O(m+n)的空间,但这任然不是最好的解决方案。
你可以设计一个用常量空间的方案吗?

原文

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

分析

第一种使用O(mn)空间的方法倒是很简单,用二位数组存储需要转换为0的所有元素的坐标,最后统一刷新就好。

void setZeroes(vector<vector<int> >& matrix) {
  vector<vector<int> > zeroes;

  for (int i = 0; i < matrix.size(); i++) {
    for (int j = 0; j < matrix[i].size(); j++) {
      if (matrix[i][j] == 0) {
    vector<int> zero;
    zero.push_back(i);
    zero.push_back(j);
    zeroes.push_back(zero);
      }
    }
  }
  for (int i = 0; i < zeroes.size(); i++) {
    for (int col = 0; col < matrix[zeroes[i][0]].size(); col++) {
      matrix[zeroes[i][0]][col] = 0;
    }
    for (int row = 0; row < matrix.size(); row++) {
      matrix[row][zeroes[i][1]] = 0;
    }
  }
}

第二种是分别记录所有等于0的元素的横坐标和纵坐标。

void setZeroes(vector<vector<int> >& matrix) {
  vector<int> rows, cols;
  int rowLen = matrix.size(), colLen = matrix[0].size();

  for (int r = 0; r < rowLen; r++) {
    for (int c = 0; c < colLen; c++) {
      if (matrix[r][c] == 0) {
    rows.push_back(r);
    cols.push_back(c);
      }
    }
  }

  for (int i = 0; i < rows.size(); i++) {
    for (int im = 0; im < colLen; im++) {
      matrix[rows[i]][im] = 0;
    }
  }
  for (int j = 0; j < cols.size(); j++) {
    for (int jm = 0; jm < rowLen; jm++) {
      matrix[jm][cols[j]] = 0;
    }
  }
}

第三种方法就是通过一个值来记录一个维度。也就是说如果某行的第一列的值等于0,就将这个值标记为0,到时候直接把这一整行都置为0。它的好处在于,等你在遍历整个二维数组的时候,你可以随意的设置第一列在各行的值,而不至于在后续的遍历中产生副作用。

也就是说,可能你是matrix[3][4]=0,也就是第三行第四列等于0,那么你可以把第四列的第一行那个值设为0,同时把第三行的第一列的值也设为0,但在下一次遍历的时候,因为第三行第一列为0了,你可以把整个第一列都置为0,所以用一个值来维护这一列的状态。代码在下文(2016/09/24)。

代码

Java

updated at 2016/09/04
    public void setZeroes(int[][] matrix) {
        int col0 = 1, rows = matrix.length, cols = matrix[0].length;

        for (int i = 0; i < rows; i++) {
            if (matrix[i][0] == 0) col0 = 0;
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }

        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 1; j--) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if (col0 == 0) matrix[i][0] = 0;
        }
    }
目录
相关文章
|
4月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
51 1
|
4月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
52 0
|
4月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
41 0
|
4月前
【LeetCode-每日一题】移除元素
【LeetCode-每日一题】移除元素
40 0
|
6月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
4天前
|
编译器 容器
哈希表模拟封装unordered_map和unordered_set
哈希表模拟封装unordered_map和unordered_set
|
4天前
|
编译器 测试技术 计算机视觉
红黑树模拟封装map和set
红黑树模拟封装map和set
|
2月前
|
存储 缓存 安全
只会“有序无序”?面试官嫌弃的List、Set、Map回答!
小米,一位热衷于技术分享的程序员,通过与朋友小林的对话,详细解析了Java面试中常见的List、Set、Map三者之间的区别,不仅涵盖了它们的基本特性,还深入探讨了各自的实现原理及应用场景,帮助面试者更好地准备相关问题。
73 20
|
2月前
|
算法
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
80 18
你对Collection中Set、List、Map理解?
|
3月前
|
存储 算法 C++
【C++】unordered_map(set)
C++中的`unordered`容器(如`std::unordered_set`、`std::unordered_map`)基于哈希表实现,提供高效的查找、插入和删除操作。哈希表通过哈希函数将元素映射到特定的“桶”中,每个桶可存储一个或多个元素,以处理哈希冲突。主要组成部分包括哈希表、哈希函数、冲突处理机制、负载因子和再散列,以及迭代器。哈希函数用于计算元素的哈希值,冲突通过开链法解决,负载因子控制哈希表的扩展。迭代器支持遍历容器中的元素。`unordered_map`和`unordered_set`的插入、查找和删除操作在理想情况下时间复杂度为O(1),但在冲突较多时可能退化为O(n)。
37 5