矩阵篇——python.刷题记录

73. 矩阵置零

1.1 核心思想

• 问题描述：给定一个二维矩阵，如果某个元素为 0，则将其所在的行和列的所有元素都置为 0。
• 解决思路：
  1. 遍历矩阵，记录哪些行和列需要被置零。
  2. 根据记录的结果，将对应的行和列置零。

1.2 具体步骤

1. 初始化记录数组：
   • row：记录哪些行需要被置零，长度为矩阵的行数 m。
   • col：记录哪些列需要被置零，长度为矩阵的列数 n。
2. 遍历矩阵，记录需要置零的行和列：
   • 如果 matrix[i][j] == 0，则将 row[i] 和 col[j] 标记为 True。
3. 根据记录结果，将矩阵置零：
   • 如果 row[i] 或 col[j] 为 True，则将 matrix[i][j] 置为 0。

2.1 时间复杂度

• 遍历矩阵记录零的位置：O(m * n)。
• 根据记录结果置零：O(m * n)。
• 总时间复杂度：O(m * n)。

2.2 空间复杂度

• 记录数组：
  • row：O(m)。
  • col：O(n)。
• 总空间复杂度：O(m + n)。

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        row, col = [False]* m, [False]* n

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    row[i] = col[j] = True
        for i in range(m):
            for j in range(n):
                if row[i] or col[j]:
                    matrix[i][j] = 0

54. 螺旋矩阵

1.1 核心思想

• 问题描述：给定一个二维矩阵，按照顺时针螺旋顺序返回所有元素。
• 解决思路：
  1. 定义四个边界：left、right、up、down，分别表示当前螺旋遍历的左、右、上、下边界。
  2. 定义四个方向：(0, 1)（向右）、(1, 0)（向下）、(0, -1)（向左）、(-1, 0)（向上）。
  3. 按照当前方向遍历矩阵，当到达边界时，调整边界并切换到下一个方向。
  4. 重复上述过程，直到遍历完所有元素。

1.2 具体步骤

1. 初始化：
   • 检查矩阵是否为空，如果为空则直接返回空列表。
   • 获取矩阵的行数 M 和列数 N。
   • 初始化四个边界：left = 0、right = N - 1、up = 0、down = M - 1。
   • 初始化结果列表 res。
   • 初始化当前位置 (x, y) 为 (0, 0)。
   • 初始化当前方向 cur_d 为 0（向右）。
2. 螺旋遍历：
   • 将当前元素 matrix[x][y] 添加到结果列表 res 中。
   • 检查是否需要切换方向：
     • 如果当前方向是向右（cur_d == 0）且到达右边界（y == right），则切换到向下方向（cur_d = 1），并将上边界 up 加 1。
     • 如果当前方向是向下（cur_d == 1）且到达下边界（x == down），则切换到向左方向（cur_d = 2），并将右边界 right 减 1。
     • 如果当前方向是向左（cur_d == 2）且到达左边界（y == left），则切换到向上方向（cur_d = 3），并将下边界 down 减 1。
     • 如果当前方向是向上（cur_d == 3）且到达上边界（x == up），则切换到向右方向（cur_d = 0），并将左边界 left 加 1。
   • 更新当前位置 (x, y) 为下一个方向的位置。
   • 重复上述过程，直到结果列表 res 的长度等于矩阵元素总数 M * N。
3. 返回结果：
   • 返回结果列表 res。

2.1 时间复杂度

• 遍历矩阵：每个元素被访问一次，时间复杂度为 O(M * N)。

2.2 空间复杂度

• 结果列表：存储所有矩阵元素，空间复杂度为 O(M * N)。
• 额外变量：仅使用常数级别的额外空间（如边界变量、方向数组等），空间复杂度为 O(1)。
• 总空间复杂度：O(M * N)（主要由结果列表决定）。

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix or not matrix[0]: return []
        M, N = len(matrix), len(matrix[0])
        left, right, up, down = 0, N - 1, 0, M - 1
        res = []
        x, y = 0, 0
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        cur_d = 0
        while len(res) != M * N:
            res.append(matrix[x][y])
            if cur_d == 0 and y == right:
                cur_d += 1
                up += 1
            elif cur_d == 1 and x == down:
                cur_d += 1
                right -= 1
            elif cur_d == 2 and y == left:
                cur_d += 1
                down -= 1
            elif cur_d == 3 and x == up:
                cur_d += 1
                left += 1
            cur_d %= 4
            x += dirs[cur_d][0]
            y += dirs[cur_d][1]
        return res

48. 旋转图像

1.1 核心思想

• 问题描述：给定一个 n x n 的二维矩阵，将其顺时针旋转 90 度。
• 解决思路：
  1. 水平翻转：将矩阵上下翻转。
  2. 主对角线翻转：将矩阵沿主对角线翻转。
  3. 经过上述两步操作后，矩阵即为顺时针旋转 90 度的结果。

1.2 具体步骤

1. 水平翻转：
   • 遍历矩阵的前半部分行（i 从 0 到 n // 2 - 1）。
   • 对于每一行，交换第 i 行和第 n - i - 1 行的元素。
   • 例如，对于矩阵：

     [1, 2, 3]
     [4, 5, 6]
     [7, 8, 9]

     水平翻转后变为：

     [7, 8, 9]
     [4, 5, 6]
     [1, 2, 3]

2. 主对角线翻转：
   • 遍历矩阵的下三角部分（i 从 0 到 n - 1，j 从 0 到 i - 1）。
   • 交换 matrix[i][j] 和 matrix[j][i]。
   • 例如，对于水平翻转后的矩阵：

     [7, 8, 9]
     [4, 5, 6]
     [1, 2, 3]

     主对角线翻转后变为：

     [7, 4, 1]
     [8, 5, 2]
     [9, 6, 3]

3. 结果：
   • 最终矩阵即为顺时针旋转 90 度的结果。

2.1 时间复杂度

• 水平翻转：遍历矩阵的前半部分行，时间复杂度为 O(n^2)。
• 主对角线翻转：遍历矩阵的下三角部分，时间复杂度为 O(n^2)。
• 总时间复杂度：O(n^2)。

2.2 空间复杂度

• 原地操作：直接在原矩阵上进行修改，未使用额外空间，空间复杂度为 O(1)。

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None
        """
        n = len(matrix)
        # 水平翻转
        for i in range(n // 2):
            for j in range(n):
                matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]
        # 主对角线翻转
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

240. 搜索二维矩阵 II

1.1 核心思想

• 问题描述：给定一个 m x n 的二维矩阵，矩阵的每一行从左到右递增，每一列从上到下递增。判断目标值 target 是否存在于矩阵中。
• 解决思路：
  1. 从矩阵的右上角（或左下角）开始搜索。
  2. 如果当前元素等于 target，返回 True。
  3. 如果当前元素小于 target，则排除当前行（因为当前行的所有元素都小于 target）。
  4. 如果当前元素大于 target，则排除当前列（因为当前列的所有元素都大于 target）。
  5. 重复上述步骤，直到找到 target 或搜索完整个矩阵。

1.2 具体步骤

1. 初始化：
   • 获取矩阵的行数 m 和列数 n。
   • 初始化指针 i 和 j，分别指向矩阵的右上角（i = 0, j = n - 1）。
2. 搜索过程：
   • 如果 matrix[i][j] == target，返回 True。
   • 如果 matrix[i][j] < target，说明当前行的所有元素都小于 target，因此向下移动一行（i += 1）。
   • 如果 matrix[i][j] > target，说明当前列的所有元素都大于 target，因此向左移动一列（j -= 1）。
3. 终止条件：
   • 如果 i 超出矩阵的行数或 j 小于 0，说明搜索完整个矩阵仍未找到 target，返回 False。

灵神的方法真的秒啊！

• 时间复杂度：O(m+n)，其中 m 和 n 分别为 matrix 的行数和列数。
• 空间复杂度：O(1)。

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        m, n = len(matrix), len(matrix[0])
        i, j = 0, n - 1  # 从右上角开始
        while i < m and j >= 0:  # 还有剩余元素
            if matrix[i][j] == target:
                return True  # 找到 target
            if matrix[i][j] < target:
                i += 1  # 这一行剩余元素全部小于 target，排除
            else:
                j -= 1  # 这一列剩余元素全部大于 target，排除
        return False