阿狗工具

1.题目

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

进阶：
一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

2.思路

2.1 方法

• 双循环
  先进行双循环查找出矩阵中出现的0所在的行和列，然后将其存储在动态数组中，然后在循环对所在的行和列进行赋值为0

3.代码

object Solution {
  def setZeroes(matrix: Array[Array[Int]]): Unit = {
    import scala.collection.mutable.ArrayBuffer
    val arrayBuffer = new ArrayBuffer[Int]()
    val arrayBuffer2 = new ArrayBuffer[Int]()
    import  scala.collection.mutable.Map
    val map = Map[Int,Int]()
    for(i<- 0 to matrix.length-1){
      for(j<- 0 to matrix(i).length-1){
        if(matrix(i)(j)==0){
          arrayBuffer.append(i)
          arrayBuffer2.append(j)
        }
      }
    }
     for(x<- arrayBuffer2.toArray) {
       // 行置为0
       for (i <- 0 to matrix.length - 1) {
         matrix(i)(x) = 0
       }
     }
    for(x<- arrayBuffer.toArray) {
      // 列置为 0
      for (j <- 0 to matrix(0).length - 1) {
        matrix(x)(j) = 0
      }
    }
  }
}

4.复杂度

• 时间复杂度O(nlogn)
• 空间复杂度O(1)