[Swift]LeetCode73. 矩阵置零 | Set Matrix Zeroes_app

概述Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place. Example 1: Input: [ [1,1,1], [1,0,1], [1,1,1]]Output: [ [1,0,1], [0,0,0], [1,0,1

Given a m x n matrix,if an element is 0,set its entire row and column to 0. Do it in-place.

Example 1:

input: [  [1,1,1],  [1,1]]Output: [  [1,  [0,0],1]]

Example 2:

input: [  [0,2,  [3,4,5,2],3,5]]Output: [  [0,0]]

Follow up:

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?

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

示例 1:

输入: [  [1,1]]输出: [  [1,1]]

示例 2:

输入: [  [0,5]]输出: [  [0,0]]

进阶:

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

40ms

 1 class Solution { 2     func setZeroes(_ matrix: inout [[Int]]) { 3         var rows = [Int]() 4         var cols = [Int]() 5          6         for i in 0 ..< matrix.count { 7             for j in 0 ..< matrix[i].count { 8                 if matrix[i][j] == 0 { 9                     rows.append(i)10                     cols.append(j)11                 }12             }13         }14         // Set rows to 015         for col in cols {16             for i in 0 ..< matrix.count {17                 matrix[i][col] = 018             }19         }20         // Set cols to 021         for row in rows {22             for j in 0 ..< matrix[row].count {23                 matrix[row][j] = 024             }25         }26     }27 }

44ms

 1 class Solution { 2     func setZeroes(_ matrix: inout [[Int]]) { 3         for i in 0..<matrix.count { 4             for j in 0..<matrix[i].count { 5                 if matrix[i][j] == 0 { 6                     matrix[i][j] = -9999 7                 }  8             } 9         }10         11         for i in 0..<matrix.count {12             for j in 0..<matrix[i].count {13                 if matrix[i][j] == -9999 {14                     for c in 0..<matrix[i].count {15                         if (matrix[i][c] != -9999) {16                             matrix[i][c] = 017                         }18                     }19                     for r in 0..<matrix.count {20                         if (matrix[r][j] != -9999) {21                             matrix[r][j] = 022                         }23                     }24                     matrix[i][j] = 025                 }26             }27         }28     }29 }

44ms

 1 class Solution { 2     func setZeroes(_ matrix: inout [[Int]]) { 3         var rows = [Int]() 4         var cols = [Int]() 5         for i in 0..<matrix.count { 6             for j in 0..<matrix[i].count { 7                 if matrix[i][j] == 0 { 8                     rows.append(i) 9                     cols.append(j)10                 }11             }12         }13         for row in rows {14             matrix[row] = Array(repeating: 0,count: matrix[row].count)15         }16         for col in cols {17             for i in 0..<matrix.count {18                 matrix[i][col] = 019             }20         }21     }22 }

48ms

 1 class Solution { 2     func setZeroes(_ matrix: inout [[Int]]) { 3         if matrix.count == 0 { 4             return 5         } 6          7         //查找第一行是否有0 8         var row0HasZore = false 9         for value in matrix[0] {10             if value == 0 {11                 row0HasZore = true12                 break13             }14         }15         16         if matrix.count > 1 {17             //查找每一行18             for i in 1..<matrix.count {19                 var rowiHasZore = false20                 //查找该行是否有0，并置第一行该列数为021                 for j in 0..<matrix[0].count {22                     if matrix[i][j] == 0 {23                         rowiHasZore = true24                         matrix[0][j] = 025                     }26                 }27                 //如果该行有0，就置该行所有数为028                 if rowiHasZore {29                     matrix[i].replaceSubrange(0..<matrix[0].count,with: [Int](repeating: 0,count: matrix[0].count))30                 }31             }32             //查找第一行是否有0，有则把整列赋值033             for j in 0..<matrix[0].count {34                 if matrix[0][j] == 0 {35                     for i in 0..<matrix.count {36                         matrix[i][j] = 037                     }38                 }39             }40         }41                     //如果第一行有0，则把该行赋值为042             if row0HasZore {43                 matrix[0].replaceSubrange(0..<matrix[0].count,count: matrix[0].count))44             }45     }46 }

76ms

 1 class Solution { 2     func setZeroes(_ matrix: inout [[Int]]) { 3         var rows = [Bool](repeating: false,count: matrix.count) 4         var cols = [Bool](repeating: false,count: matrix[0].count) 5         for (i,row) in matrix.enumerated() { 6             for (j,num) in row.enumerated() { 7                 if num == 0 { 8                     rows[i] = true 9                     cols[j] = true10                 }11             }12         }13         for (i,row) in matrix.enumerated() {14             for (j,_) in row.enumerated() {15                 if rows[i] || cols[j] {16                     matrix[i][j] = 017                 }18             }19         }20     }21 }

160ms

 1 class Solution { 2     func setZeroes(_ matrix: inout [[Int]]) { 3         var isCol:Bool = false 4         var R:Int =  matrix.count 5         var C:Int =   matrix[0].count 6         for i in 0..<R 7         { 8             //因为第一行和第一列的第一个单元是相同的，即矩阵[0][0] 9             //我们可以为第一行/列使用一个附加变量。10             //对于这个解决方案，我们使用第一列的附加变量。11             //使用第一行的矩阵[0][0]12             if matrix[i][0] == 0 {isCol = true}13             for j in 1..<C14             {15                 //如果元素为零，则将相应行和列的第一个元素设置为016                 if matrix[i][j] == 017                 {18                     matrix[0][j] = 019                     matrix[i][0] = 020                 }21             }22         }23         //再次迭代数组并使用第一行和第一列，更新元素24         for i in 1..<R25         {26             for j in 1..<C27             {28                 if matrix[i][0] == 0 || matrix[0][j] == 029                 {30                     matrix[i][j] = 031                 }32             }33         }34         //是否需要将第一行设置为035         if matrix[0][0] == 036         {37             for j in 0..<C38             {39               matrix[0][j] = 0  40             }41         }42         //是否需要将第一列设置为043         if isCol44         {45             for i in 0..<R46             {47                 matrix[i][0] = 048             }49         }50     }51 }

236ms

 1 class Solution { 2     func setZeroes(_ matrix: inout [[Int]]) { 3          4         for i in matrix.indices { 5             for j in matrix[i].indices { 6                 //print(i,j,matrix[i][j]) 7                 if matrix[i][j] == 0 { 8                     helper(&matrix,i,1) 9                     helper(&matrix,2)10                     helper(&matrix,3)11                     helper(&matrix,4)12                 }13             }14         }15         16         //print(matrix)17         for i in matrix.indices {18             for j in matrix[i].indices {19                 if matrix[i][j] == Int.max {20                     matrix[i][j] = 021                 }22             }23         }24     }25     26     func helper(_ matrix: inout[[Int]],_ i: Int,_ j: Int,_ dir: Int) {27         //print(i,dir)28         var i = i29         var j = j30         if dir == 1 {31             while i >= 0 {32                 if (matrix[i][j] != 0) {33                     matrix[i][j] = Int.max    34                 }35                 36                 i -= 137             }38         } else if dir == 2 {39             while i < matrix.count {40                 if (matrix[i][j] != 0) {41                     matrix[i][j] = Int.max42                 }43                 i += 144             }45         } else if dir == 3 {46             while j >= 0 {47                 if (matrix[i][j] != 0) {48                     matrix[i][j] = Int.max49                 }50                 j -= 151             }52         } else {53             while j < matrix[i].count {54                 if (matrix[i][j] != 0) { 55                     matrix[i][j] = Int.max56                 }57                 j += 158             }59         }60     }61 }