LeetCode – 73. Set Matrix Zeroes

題目連結: https://leetcode.com/problems/set-matrix-zeroes/

參考解法: https://zxi.mytechroad.com/blog/algorithms/array/leetcode-73-set-matrix-zeroes/

法ㄧ(Space complexity: O(mn))

    func setZeroes(_ matrix: inout [[Int]]) {
    	var rows: Set<Int> = []
    	var cols: Set<Int> = []
        for i in 0 ..< matrix.count {
        	for j in 0 ..< matrix[0].count {
        		if matrix[i][j] == 0 {
        			rows.insert(i)
        			cols.insert(j)
        		}
        	}
        }

        for col in cols {
        	for i in 0 ..< matrix.count {
        		matrix[i][col] = 0
        	}
        }

        for row in rows {
        	for j in 0 ..< matrix[0].count {
        		matrix[row][j] = 0
        	}
        }
    }

法二(Space complexity: O(1)) 參考自Ref

    func setZeroes(_ matrix: inout [[Int]]) {
    	var row0 = false
    	var col0 = false

    	for i in 0 ..< matrix.count {
    		if matrix[i][0] == 0 {
    			col0 = true
    			break
    		}
    	}

    	for j in 0 ..< matrix[0].count {
    		if matrix[0][j] == 0 {
    			row0 = true
    			break
    		}
    	}

    	for i in 1 ..< matrix.count {
    		for j in 1 ..< matrix[0].count {
    			if matrix[i][j] == 0 {
    				matrix[i][0] = 0
    				matrix[0][j] = 0
    			}
    		}
    	}

    	for i in 1 ..< matrix.count {
    		for j in 1 ..< matrix[0].count {
    			if matrix[i][0] == 0 || matrix[0][j] == 0 {
    				matrix[i][j] = 0
    			}
    		}
    	}

    	if row0 {
    		for j in 0 ..< matrix[0].count {
    			matrix[0][j] = 0
    		}
    	}

    	if col0 {
    		for i in 0 ..< matrix.count {
    			matrix[i][0] = 0
    		}
    	}
    }