旋转图像

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

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

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

尝试

方法

先上下翻转再沿主对角线翻转

代码

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)

        # Step 1: 上下翻转
        for i in range(n // 2):
            matrix[i], matrix[n - i - 1] = matrix[n - i - 1], matrix[i]

        # Step 2: 沿主对角线翻转
        for i in range(n):
            for j in range(i + 1, n):  # 注意这里限制 j > i
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

注意

在沿主对角线翻转部分：如果没有限制 $j > i$，会导致对角线的元素被重复交换两次（每次都恢复原位），也浪费了一些计算资源。应该将内层循环限制为 for j in range(i+1, n)，避免重复交换。

杂度分析

• 时间复杂度：两部分分别是 $O(n^2)$ 的行交换和对角线交换，总时间复杂度为 $O(n^2)$。
• 空间复杂度：$O(1)$，没有使用额外空间。

搜索二维矩阵 II

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

暴力遍历

代码

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == target:
                    return True
        else:
            return False

时间复杂度

• 你的代码需要遍历整个矩阵，时间复杂度为 $O(m \times n)$，其中 $m$ 是行数，$n$ 是列数。
• 当矩阵很大时，这种方法会非常耗时。

空间复杂度

• 空间复杂度为 $O(1)$，因为没有使用额外的存储空间。

不足

• 没有利用矩阵元素的排序性质（每行从左到右、每列从上到下递增）。
• 在最坏情况下，所有元素都会被检查，这样的效率无法满足题目要求的“高效算法”。

优化

思路

选择右上角作为起点：

• 从右上角出发，向左的元素变小，向下的元素变大。
• 如果当前元素比目标值小，则向下移动（排除当前行）。
• 如果当前元素比目标值大，则向左移动（排除当前列）。
• 如果找到目标值，则返回 True。

选择左下角作为起点（类似思路）：

• 从左下角出发，向右的元素变大，向上的元素变小。
• 如果当前元素比目标值小，则向右移动。
• 如果当前元素比目标值大，则向上移动。
• 如果找到目标值，则返回 True。

代码

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False

        m, n = len(matrix), len(matrix[0])
        row, col = 0, n - 1  # 从右上角开始

        while row < m and col >= 0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                col -= 1  # 向左移动
            else:
                row += 1  # 向下移动

        return False

复杂度

• 时间复杂度：$O(m + n)$，因为最多需要移动 $m + n$ 步。
• 空间复杂度：$O(1)$，不使用额外空间。

注意

在代码中的 while 要使用 and 连接，使用 or 会越界。