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.

        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?

 

        思路：要找到矩阵中值为0的元素，并将其所在的行和列中的所有元素都置为0。

        在扫描每一行的过程中，如果边扫描，边置0，则后续扫描每一列的时候，无法区分当前元素是原值为0，还是后置为0的。

        首先想到这种方法，利用长度为n的哈希表，按行扫描，针对每一行中值为0的元素，将其所在的列索引记录到哈希表中，扫描完本行之后，如果该行包含值为0的元素，则将本行所有元素置为0。扫描完所有行之后，根据哈希表中的列索引，将其中每列上所有元素都置为0。

         题目要求空间复杂度为O(1)，这稍微增加了一些的难度，上面的那种思路，还需要额外的哈希空间记录列索引。但是，因包含0元素的行最终都会被全置0，本身就是可利用的空间。所以，可以将找到的第一个值为0的元素所在的行，当做缓存空间即可。

        一般情况下，像这种确实需要额外的空间，但有要求空间复杂度为O(1)的，首先就应该想到要利用原有空间。

        代码如下：

void setZeroes(int** matrix, int matrixRowSize, int matrixColSize) 
{
    int bufrow = -1;
    int set0flag = 0;
    int i, j;

    for(i = 0; i < matrixRowSize; i++)
    {
        for(j = 0; j < matrixColSize; j++)
        {
            if(matrix[i][j] == 0)
            {
                if(bufrow == -1)
                {
                    bufrow = i;
                    break;
                }
                else
                {
                    matrix[bufrow][j] = 0;
                    set0flag = 1;
                }
            }
        }
        
        if(set0flag)
        {
            memset(matrix[i], 0, sizeof(int) * matrixColSize);
            set0flag = 0;
        }
    }

    if(bufrow != -1)
    {
        for(j = 0; j < matrixColSize; j++)
        {
            if(matrix[bufrow][j] == 0)
            {
                for(i = 0; i < matrixRowSize; i++)
                {
                    matrix[i][j] = 0;
                }
            }
        }
        memset(matrix[bufrow], 0, sizeof(int) * matrixColSize);
    }   
}