本文主要是介绍leetcode 73 Set Matrix Zeros 矩阵置零，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
leetcode 73 Set Matrix Zeros
原题链接 https://leetcode.com/problems/set-matrix-zeroes/
题目描述
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
m x n的数组，如果某元素是0，则将其所在的行和列的所有元素置零。
题目中给出了要求，Did you use extra space?
- A straight forward solution using O(mn) space is probably a bad idea.
使用另一个m*n的数组，不好 - A simple improvement uses O(m + n) space, but still not the best solution.
使用大小为m+n的额外空间，还不是最优解 - Could you devise a constant space solution?
能否用常量级的空间来解决？
关于不好的解法
显然题目要求中指明了三中解法，其中前两种均为不好的解法。不过我们这里还是简单说一下。
使用O(m*n)空间的解法
- 假设原始数据为X[m][n]，复制一份数据到Y[m][n]
- 然后遍历Y，根据其中的元素来对X中的元素进行置零。
空间复杂度O(m*n)；对于时间复杂度，复制需要O(m*n)，然后遍历Y并处理X是O(m*n*(m+n))。可见空间复杂度和时间复杂度都不好。
使用O(m+n)空间的解法
- 使用数组X[m]来记录某一列是否需要置零，用Y[n]来记录某一行是否需要置零
- 遍历原始数据，如果某一元素为0，则修改X和Y中相应的标记位。
- 遍历X，如果标记为真则对原始数据中的相应列进行置零
- 遍历Y，如果标记为真则对原始数据中的相应行进行置零
这个算法的空间复杂度为O(m+n)，时间复杂度O(m*n)。
这篇关于leetcode 73 Set Matrix Zeros 矩阵置零的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
