循环轮转矩阵

标签: 数组 矩阵 模拟

难度: Medium

给你一个大小为 m x n 的整数矩阵 grid​​​ ，其中 m 和 n 都是 偶数 ；另给你一个整数 k 。

矩阵由若干层组成，如下图所示，每种颜色代表一层：

矩阵的循环轮转是通过分别循环轮转矩阵中的每一层完成的。在对某一层进行一次循环旋转操作时，层中的每一个元素将会取代其 逆时针 方向的相邻元素。轮转示例如下：

返回执行 k 次循环轮转操作后的矩阵。

 

示例 1：

输入：grid = [[40,10],[30,20]], k = 1
输出：[[10,20],[40,30]]
解释：上图展示了矩阵在执行循环轮转操作时每一步的状态。

示例 2：

输入：grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
输出：[[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
解释：上图展示了矩阵在执行循环轮转操作时每一步的状态。

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 50
  • m 和 n 都是 偶数
  • 1 <= grid[i][j] <= 5000
  • 1 <= k <= 109

Submission

运行时间: 107 ms

内存: 16.5 MB

class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        i, j, h, p = 0, 0, m - 1, n - 1
        for _ in range(min(m, n) // 2):
            temp = []
            for jj in range(j, p):
                temp.append(grid[i][jj])
            for jj in range(i, h):
                temp.append(grid[jj][p])
            for jj in range(p, j, -1):
                temp.append(grid[h][jj])
            for jj in range(h, i, -1):
                temp.append(grid[jj][j])
            loop = k % len(temp)
            temp = temp[loop:] + temp[:loop]
            for jj in range(j, p):
                val = temp.pop(0)
                grid[i][jj] = val
            for jj in range(i, h):
                val = temp.pop(0)
                grid[jj][p] = val
            for jj in range(p, j, -1):
                val = temp.pop(0)
                grid[h][jj] = val
            for jj in range(h, i, -1):
                val = temp.pop(0)
                grid[jj][j] = val
            i += 1
            j += 1
            h -= 1
            p -= 1
        return grid

Explain

该题解采用了层次遍历的方式，按照从外层到内层的顺序，逐层进行旋转操作。对于每一层，首先将该层的元素按照逆时针方向存储到一个临时数组中，然后根据旋转次数k对临时数组进行旋转操作（实际上是将数组分成两部分，然后重新拼接），最后将旋转后的数组元素按照原来的顺序放回到矩阵中。

时间复杂度: O(m * n)

空间复杂度: O(min(m, n))

class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        i, j, h, p = 0, 0, m - 1, n - 1
        for _ in range(min(m, n) // 2):
            temp = []
            for jj in range(j, p):
                temp.append(grid[i][jj])
            for jj in range(i, h):
                temp.append(grid[jj][p])
            for jj in range(p, j, -1):
                temp.append(grid[h][jj])
            for jj in range(h, i, -1):
                temp.append(grid[jj][j])
            loop = k % len(temp)
            temp = temp[loop:] + temp[:loop]
            for jj in range(j, p):
                val = temp.pop(0)
                grid[i][jj] = val
            for jj in range(i, h):
                val = temp.pop(0)
                grid[jj][p] = val
            for jj in range(p, j, -1):
                val = temp.pop(0)
                grid[h][jj] = val
            for jj in range(h, i, -1):
                val = temp.pop(0)
                grid[jj][j] = val
            i += 1
            j += 1
            h -= 1
            p -= 1
        return grid

Explore

使用逆时针方向存储每一层的元素有助于简化旋转操作，因为它使得数组可以直接通过简单的偏移来实现旋转。在旋转矩阵时，若顺时针旋转目标是将部分元素向前移动，逆时针存储后，这种前移操作就转化为了数组的后移操作，这可以通过数组的切片和拼接简单实现。此外，这种存储方式还保持了元素在矩阵中的逻辑位置关系，使得旋转后的元素重新放回矩阵时位置匹配更直观，减少了计算和错误的可能。

在题解中，旋转操作首先计算了旋转次数k对数组长度的余数，即`k % len(temp)`。这个操作得到了实际需要旋转的步数，防止了多余的全圈旋转。接着，题解使用数组的切片操作来进行旋转：将数组从`loop`位置切开，然后将切开的两部分数组重新拼接，前半部分变成了原数组的后半部分，后半部分则变成了前半部分。这样，原本在数组前面的`loop`个元素通过切片操作放置到了数组的末尾，实现了逆时针旋转的效果。

进行`k % len(temp)`的目的是为了优化旋转次数，避免无效的全圈旋转。因为当旋转次数k等于数组长度`len(temp)`时，经过完整的旋转后数组将恢复到原始状态，无需任何改变。如果不进行模长操作，当k大于数组长度时，数组将进行多次无效的全圈旋转，导致计算浪费时间和资源。例如，如果数组长度是100，旋转次数是300，那么实际有效的旋转次数只有300 % 100 = 0次，即不需要任何旋转。不进行模长操作将导致不必要的计算，尤其在k远大于数组长度时更为明显。