《leetCode-php》替换矩阵中0的行和列都为0

给定一个m*n的矩阵，如果有一个元素是0，就把该元素所在的行和列上的元素全置为0，要求使用原地算法。 

拓展： 

你的算法有使用额外的空间吗？ 

一种比较直接的算法是利用O(m,n)的空间，但是这不是一个好的解法 

使用简单的改进可以在O(m+n)的空间解决这个问题，但是还不是最佳的解法 

你能在常量级的空间复杂度内解决这个问题吗？

利用数组本来的位置，空间复杂度为O(1)

<?php /** * @param $arrMatrix * @return array * @brief 这道题不是只有一个0,而是有多个0 */ function setZeroes($arrMatrix) { $width = count($arrMatrix); $length = count($arrMatrix[0]); //第一列是否有0 $widFlag = 0; for ($i = 0; $i < $width; $i ++) { if ($arrMatrix[$i][0] == 0) { $widFlag = 1; } } //第一行是否有0 $lenFlag = 0; for ($i = 0; $i < $length; $i ++) { if ($arrMatrix[0][$i] == 0) { $lenFlag = 1; } } //有0的位置都映射到第一行和第一列 for ($i = 1; $i < $width; $i ++) { for ($j = 1; $j < $length; $j ++) { if ($arrMatrix[$i][$j] == 0) { $arrMatrix[0][$j] = 0; $arrMatrix[$i][0] = 0; } } } //对第一列查找那些行要置为0 for ($i = 0; $i < $width; $i ++) { if ($arrMatrix[$i][0] == 0) { for ($j = 1; $j < $length; $j ++) { $arrMatrix[$i][$j] = 0; } } } //对第一行查找那些列要置为0 for ($i = 0; $i < $length; $i ++) { if ($arrMatrix[0][$i] == 0) { for ($j = 1; $j < $width; $j ++) { $arrMatrix[$j][$i] = 0; } } } //如果第一行和第一列中原来有0,则需要把他们也全部置为0 if ($widFlag == 1) { for ($i = 0; $i < $width; $i ++) { $arrMatrix[$i][0] = 0; } } if ($lenFlag == 1) { for ($i = 0; $i < $length; $i ++) { $arrMatrix[0][$i] = 0; } } return $arrMatrix; } $arr = [ [1,0,1,1,1,1], [1,1,1,1,0,1], [1,1,1,1,1,1], ]; $ret = setZeroes($arr); print json_encode($ret);

可以增加一个标志位，空间复杂度是O(m+n)

<?php /** * @param $arrMatrix * @return array * @brief 这道题不是只有一个0,而是有多个0 */ function setZeroes($arrMatrix) { $width = count($arrMatrix); $length = count($arrMatrix[0]); $arrFlag = array(); //有0的位置都映射到第一行和第一列 for ($i = 0; $i < $width; $i ++) { for ($j = 0; $j < $length; $j ++) { if ($arrMatrix[$i][$j] == 0) { $arrFlag[-1][$j] = 0; $arrFlag[$i][-1] = 0; } } } //对第一列查找那些行要置为0 for ($i = 0; $i < $width; $i ++) { if (isset($arrFlag[$i][-1]) && $arrFlag[$i][-1] == 0) { for ($j = 0; $j < $length; $j ++) { $arrMatrix[$i][$j] = 0; } } } //对第一行查找那些列要置为0 for ($i = 0; $i < $length; $i ++) { if (isset($arrFlag[-1][$i]) && $arrFlag[-1][$i] == 0) { for ($j = 0; $j < $width; $j ++) { $arrMatrix[$j][$i] = 0; } } } return $arrMatrix; } $arr = [ [1,0,1,1,1,1], [1,1,1,1,0,1], [1,1,1,1,1,1], ]; $ret = setZeroes($arr); print json_encode($ret);