LeetCode -- Set Matrix Zeroes

LeetCode -- 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*n的矩陣，判斷如果matrix[i,j]為0（i∈[0,m) , j∈[0,n)），則把它的整行和整列都標記為0。


思路：
第一次遍歷：使用隊列存值為0的位置
第二次遍歷，遍歷隊列進行標記。


空間復雜度為O(n^2)


這裡有一個空間復雜度為常數的解法，但是可讀性不夠強因此不推薦，如果空間允許的情況下，依然推薦使用O(n^2)空間復雜度的解法。


實現代碼：

public class Solution {
    public void SetZeroes(int[,] matrix) 
    {
    	var row = matrix.GetLength(0);
    	var col = matrix.GetLength(1);
    	if(row <= 1 && col <= 1){
    		return;
    	}
    	
    	var q = new Queue();
    	for(var i = 0;i < row; i++){
    		for(var j = 0;j < col; j++){
    			if(matrix[i,j] == 0){
    				q.Enqueue(new Pos(i,j));
    			}
    		}
    	}
    	
    	while(q.Count > 0){
    		var pos = q.Dequeue();
    		for(var i = pos.row;i >=0; i--){
    			matrix[i,pos.col] = 0;
    		}
    		for(var i = pos.row;i < row; i++){
    			matrix[i,pos.col] = 0;
    		}
    		for(var i = pos.col;i >=0; i--){
    			matrix[pos.row,i] = 0;
    		}
    		for(var i = pos.col;i < col; i++){
    			matrix[pos.row,i] = 0;
    		}
    	}
    }


    public class Pos{
    	public Pos(int r, int c)
    	{
    		row = r;
    		col = c;
    	}
    	public int row;
    	public int col;
    }


}