package daily

fun main() {
    // 面试题 01.08. 零矩阵
    // https://leetcode.cn/problems/zero-matrix-lcci/

    val matrix = arrayOf(arrayOf(0,1,2,0).toIntArray(), arrayOf(3,4,5,2).toIntArray(), arrayOf(1,3,1,5).toIntArray())
    setZeroes1(matrix)
    println(matrix.contentDeepToString())
}

fun setZeroes(matrix: Array<IntArray>): Unit {
    if (matrix.isEmpty()) {
        return
    }

    val rowSet = HashSet<Int>()
    val columnSet = HashSet<Int>()

    for (i in matrix.indices) {
        for (j in matrix[0].indices) {
            if (matrix[i][j] == 0) {
                rowSet.add(i)
                columnSet.add(j)
            }
        }
    }

    for (rowIndex in rowSet) {
        for (j in matrix[0].indices) {
            matrix[rowIndex][j] = 0
        }
    }

    for (columnIndex in columnSet) {
        for (i in matrix.indices) {
            matrix[i][columnIndex] = 0
        }
    }
}

fun setZeroes1(matrix: Array<IntArray>): Unit {
    if (matrix.isEmpty()) {
        return
    }
    var firstRowContains0 = false
    var firstColumnContains0 = false

    for (rowIndex in matrix.indices) {
        for (columnIndex in matrix[rowIndex].indices) {
            if (matrix[rowIndex][columnIndex] == 0) {
                if (rowIndex == 0) {
                    // 第一行包含0
                    firstRowContains0 = true
                }
                if (columnIndex == 0) {
                    // 第一列包含0
                    firstColumnContains0 = true
                }
                // 用第一行、第一列作为标识位
                matrix[0][columnIndex] = 0
                matrix[rowIndex][0] = 0
            }
        }
    }
    for (rowIndex in 1 until matrix.size) {
        if (matrix[rowIndex][0] == 0) {
            for (columnIndex in 1 until matrix[rowIndex].size) {
                matrix[rowIndex][columnIndex] = 0
            }
        }
    }

    for (columnIndex in 1 until matrix[0].size) {
        if (matrix[0][columnIndex] == 0) {
            for (rowIndex in 1 until  matrix.size) {
                matrix[rowIndex][columnIndex] = 0
            }
        }
    }

    if (firstColumnContains0) {
        for (rowIndex in matrix.indices) {
            matrix[rowIndex][0] = 0
        }
    }
    if (firstRowContains0) {
        for (columnIndex in matrix[0].indices) {
            matrix[0][columnIndex] = 0
        }
    }
}