Leetcode【73、74】
问题描述：【Array】73. Set Matrix Zeroes
解题思路：
给一个 m*n 矩阵，将 0 所在的行和列元素都置为 0。
首先这题最重要的一点，是如何处理置 0 后，不会影响后续遍历结果。也就是要避免在某次操作中我将 a[i][j] 置 0，而之后我遍历到 a[i][j] 元素时，其原本的值丢失，导致最后数组所有元素都是 0。
方法1：空间复杂度为 O(m*n)，时间复杂度为 O(m*n*max(m,n))
扫描原矩阵，将元素为 0 的下标 [i, j] 保存到数组中（最多有 m* n 个 0）。遍历数组，将原矩阵的行 i 和列 j 的元素置 0。
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
m, n = len(matrix), len(matrix[0])
zeros = [] # 保存 0 元素下标 (i, j)
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
zeros.append((i,j))
for zero in zeros: # 遍历数组
for j in range(n): # 所在行 zero[0] 置 0
matrix[zero[0]][j] = 0
for i in range(m): # 所在列 zero[1] 置 0
matrix[i][zero[1]] = 0方法2：空间复杂度为 O(m+n)，时间复杂度为 O(m*n)
比起方法 1，可以将 0 所在的行 i 和 列 j 分别记录到两个数组中。然后，分别遍历这两个数组，将行和列分别置 0。这样空间复杂度为 O(m+n)，时间复杂度为 O(m*n)。
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
m, n = len(matrix), len(matrix[0])
row, col = [], [] # 分别记录原数组 0 元素的行跟列
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
row.append(i)
col.append(j)
for r in row: # 所在行 r 置 0
for j in range(n):
matrix[r][j] = 0
for c in col: # 所在行 c 置 0
for i in range(m):
matrix[i][c] = 0方法3：空间复杂度为 O(1)，时间复杂度为 O(m*n)
如何不开辟空间也可以完成置 0 操作呢？就要保证原矩阵后续的 0 不受前面元素 0 的影响。因此，可以在遍历原矩阵遇到一个 0 时，将该 0 所在的行和列、除 0 以外的其他元素都置为一个特殊值（如 float("inf") 或者 float("-inf")）。然后，再操作一次原数组，将所有特殊值置为 0 即可。因为是在原数组上操作的，空间复杂度为 O(1)。
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
m, n = len(matrix), len(matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
for col in range(n):
if matrix[i][col] != 0: # 除了 0 以外的其他元素都置为特殊值
matrix[i][col] = float("inf")
for row in range(m): # 除了 0 以外的其他元素都置为特殊值
if matrix[row][j] != 0:
matrix[row][j] = float("inf")
for i in range(m):
for j in range(n):
if matrix[i][j] == float("inf"): # 将特殊值置为 0
matrix[i][j] = 0问题描述：【Array、Binary Search】74. Search a 2D Matrix
解题思路：
这道题是给一个 m*n 的矩阵，矩阵的行和列的元素都是升序排列，查找是否存在一个数 target。
首先，O(m*n) 的时间复杂度肯定先排除。
方法1（时间复杂度 O(m+n)）：
由于矩阵的特殊性，可以先定位 target 所在的行，然后再在列中查找。定位行时，可以比较 target 与每一行的最后一个元素，如果该行的最后一个元素大于等于 target，则说明该行就是 target 所在的行。定位列时，从该行最后一个元素往前搜索，直到找到 target 所在的列。如果在搜索过程中该行元素小于 target，说明 target 不存在，返回 -1。这样，时间复杂度为 O(m+n)。
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix: # []
return False
m, n = len(matrix), len(matrix[0])
if n == 0: # [[]]
return False
i, j = 0, n-1
while i < m: # 定位 target 所在的行
if matrix[i][-1] < target:
i += 1
else:
break
if i == m: # target > matrix[m-1][n-1]
return False
while j >= 0:
if matrix[i][j] == target:
return True
elif matrix[i][j] > target:
j -= 1
else:
return False
return False # target < matrxi[i][0]方法2（时间复杂度 O(log(m*n) = O(logm + logn))）：
因为如果把二维矩阵按照从左到右、从上到下进行排列，得到的序列也是升序的，因此这道题可以使用二分查找。二分查找的区间就是 A[0, m*n-1] 这 m*n 个元素。因此，此题的难点就在于中间元素索引 mid 的值 mid_val 与矩阵元素的对应关系。不难发现，mid_val = A[mid/n][mid%n]。然后套用二分查找的模板比较 mid_val 与 target 即可。时间复杂度为 O(log (m*n))，即 O(logm + logn)。
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix: # []
return False
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = left + (right - left) // 2
mid_val = matrix[mid//n][mid%n]
if mid_val == target:
return True
elif mid_val < target:
left = mid + 1
else:
right = mid - 1
return False腾讯云开发者
