矩阵清零--进军硅谷

给定一个二维的m*n矩阵,如果某个元素为0,那么将其所在行和列的所有元素设为0。不允许使用额外空间。

刚看到这题,只想到开两个数组,一个用来记录要设为0的行,一个用来记录要设为0的列,但是这需要使用额外空间。书中解法,利用了已有数组,首先找到一个位0的元素,记录其所在的行与列的位置,然后在后面的扫描过程中,如果某个元素为0,则把第一个为0的行与此元素的列的位置设为0,把第一个为0的列与此元素的行的位置设为0,第二遍扫描的时候,跳过第一个为0的行与列的元素,如果某个元素在第一个为0元素的行与此元素的列或者第一个为0元素的列与此元素的行的位置为0则把此元素设为0,最后设置第一个为0的元素的行与列全为0.

原文地址:https://www.cnblogs.com/wen-ge/p/4907485.html