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