力扣100题-矩阵

1.矩阵置零

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

思路一：

• 使用两个标记数组，，用矩阵的第一行和第一列代替两个标记数组，分别表示每一行，每一列是否要置为零，遍历矩阵，更新标记数组，再用标记数组来更新矩阵。达到O(1)的额外空间。
• 代码：

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m = len(matrix)
        n = len(matrix[0])
        # 先特殊处理第一行和第一列
        flag_col0 = any(matrix[i][0] == 0 for i in range(m))
        flag_row0 = any(matrix[0][i] == 0 for i in range(n))
		# 遍历矩阵，把0存在对应的第一行和第一列上
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0
        #更新矩阵
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        # 回过头更新第一行和第一列
        if flag_col0:
            for i in range(m):
                matrix[i][0] = 0
        if flag_row0:
            for j in range(n):
                matrix[0][j] = 0

2.螺旋矩阵

• 描述：给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

思路一：

• 发现顺序是有一定规律的，即都是从左到右，从上到下，从右到左，从下到上的不断循环，可以设置四个边界，一旦某两个相对的边界越过后，循环结束
• 代码：

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix: return []
        n = len(matrix)
        m = len(matrix[0])
        l, r, t, b = 0, m - 1, 0, n - 1
        res = list()
        while True:
            # 从左到右
            for i in range(l, r + 1):
                res.append(matrix[t][i])
            t += 1
            if t > b:
                break
            # 从上到下
            for i in range(t, b + 1):
                res.append(matrix[i][r])
            r -= 1
            if r < l:
                break
            # 从右到左
            for i in range(r, l - 1, -1):
                res.append(matrix[b][i])
            b -= 1
            if b < t:
                break
            # 从下到上
            for i in range(b, t - 1, -1):
                res.append(matrix[i][l])
            l += 1
            if l > r:
                break
        return res

3.旋转图像

• 描述：给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

  你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

思路一：

• 可以发现先对矩阵进行上下翻转再进行按对角线翻转即可实现顺时针的旋转90度
• 代码：

class Solution:
    def rotate(self, matrix: List[List[int]]) -> 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]

4.搜索二维矩阵||

• 描述：编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

思路一：

• 由于每行都是有序的，可以利用bisect模块对每行进行二分查找，时间复杂度为O(mlogn)
• 代码：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            idx = bisect_left(row, target)
            if idx < len(row) and row[idx] == target: # 当target大于所有这一行的数，idx为len(row),会导致索引越界，需要提前判读
                return True
        return False

思路二：

• 思路一中没有利用好每一列之间也是升序的。可以从右上角（0，n-1）的元素tmp开始搜索，当target<tmp时，那么tmp所在的列都一定比target大，y -= 1;当target>tmp时，tmp所在的行都比target小，x += 1。相当于一个Z字型走法，完美地利用了两个升序条件，时间复杂度为O(m+n)。
• 代码：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        x, y = 0, n - 1
        while x < m and y >= 0: # 设置边界
            if matrix[x][y] == target:
                return True
            if matrix[x][y] < target:
                x += 1
            else:
                y -= 1
        return False

小节：

• 矩阵一般在于空间的优化，在原地进行操作，那么就要对要求的操作进行找规律或是直接利用原先矩阵的空间
• 也会涉及到旋转，翻转等操作，要找规律变换
• 矩阵也相当于一个二维数组，进行一些数组操作