二维网格迁移

难度: Easy

给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。

每次「迁移」操作将会引发下述活动：

位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]。
位于 grid[m - 1][n - 1] 的元素将会移动到 grid[0][0]。

请你返回 k 次迁移操作后最终得到的 二维网格。

示例 1：

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

示例 2：

输入：grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
输出：[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

示例 3：

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

提示：

m == grid.length
n == grid[i].length
1 <= m <= 50
1 <= n <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100

Submission

运行时间: 27 ms

内存: 16.6 MB

from typing import List

class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        flattened = [elem for row in grid for elem in row]  # Flatten the grid into a 1D list
        total_elements = m * n
        
        # Perform the shifting operation k times
        k %= total_elements  # Only need to shift for k mod total_elements times
        flattened = flattened[-k:] + flattened[:-k]  # Shift the elements
        
        # Convert the flattened list back into a 2D grid
        result = []
        for i in range(0, total_elements, n):
            row = flattened[i:i+n]
            result.append(row)
        
        return result

solution = Solution()

grid1 = [[1,2,3],[4,5,6],[7,8,9]]
k1 = 1
print(solution.shiftGrid(grid1, k1))  # [[9, 1, 2], [3, 4, 5], [6, 7, 8]]

grid2 = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]]
k2 = 4
print(solution.shiftGrid(grid2, k2))  # [[12, 0, 21, 13], [3, 8, 1, 9], [19, 7, 2, 5], [4, 6, 11, 10]]

grid3 = [[1,2,3],[4,5,6],[7,8,9]]
k3 = 9
print(solution.shiftGrid(grid3, k3))  # [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Explain

题解通过将二维网格展平成一维列表，然后进行元素的循环移位来解决问题。首先，将网格的所有行展平成一个列表。然后，利用 Python 的切片操作对列表进行旋转，只需要移动 k mod (m*n) 次，因为超过网格总元素数的移动是冗余的。最后，将调整后的一维列表重新构造成 m 行 n 列的二维网格。这种方法直接操作列表元素，避免了逐个元素复杂的索引计算。

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

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

from typing import List

class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])  # 获取网格的行数和列数
        flattened = [elem for row in grid for elem in row]  # 将二维网格转换为一维列表
        total_elements = m * n  # 计算总元素数

        # 对移动次数进行取模优化
        k %= total_elements  # 实际的移动次数为 k mod total_elements
        # 列表切片进行元素移动
        flattened = flattened[-k:] + flattened[:-k]  # 将列表后 k 个元素移动到前面

        # 将一维列表重新构造为二维网格
        result = []
        for i in range(0, total_elements, n):
            row = flattened[i:i+n]
            result.append(row)

        return result

solution = Solution()

grid1 = [[1,2,3],[4,5,6],[7,8,9]]
k1 = 1
print(solution.shiftGrid(grid1, k1))  # [[9, 1, 2], [3, 4, 5], [6, 7, 8]]

grid2 = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]]
k2 = 4
print(solution.shiftGrid(grid2, k2))  # [[12, 0, 21, 13], [3, 8, 1, 9], [19, 7, 2, 5], [4, 6, 11, 10]]

grid3 = [[1,2,3],[4,5,6],[7,8,9]]
k3 = 9
print(solution.shiftGrid(grid3, k3))  # [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Explore

使用 k mod (m*n) 是为了优化性能和避免冗余操作。因为二维网格展平后的一维列表长度为 m*n，当移动次数 k 大于等于 m*n 时，完成一整轮移动后网格会恢复原状，因此只需考虑 k mod (m*n) 余下的移动次数。如果直接使用 k 而 k 大于 m*n，那么很多移动是重复的，没有实际效果，会导致不必要的计算开销。

列表切片操作通过将原列表分为两部分：最后 k 个元素和前面剩余的元素，然后将这两部分重新连接。具体操作为先取 `-k:`（最后 k 个元素），再取 `:-k`（除最后 k 个元素以外的前面的元素），这样重新组合后的列表正好模拟了元素向右移动 k 位置的结果。这种操作确保了每个元素都正确移动到了应该在的新位置。

是的，这个算法同样有效，即使对于非常小的网格如 1x1。算法首先将网格转换为一维列表，对于空网格转换结果为空列表，对于 1x1 网格转换结果为单元素列表。在这两种情况下，应用切片操作和重新构造二维网格的过程仍然适用，不会引发任何错误或异常。对于空网格，结果仍然是空；对于 1x1 网格，无论 k 是多少，结果都是原网格，因为只有一个元素，无法实际移动。

如果 k 为 0，算法中的 `k %= total_elements` 将导致 k 保持为 0。后续的切片操作 `-k:` 和 `:-k` 将分别解释为整个列表和空列表，所以最终的操作是将整个列表和一个空列表连接，这本质上没有改变列表。虽然技术上进行了一些计算，但这些步骤很简单，对性能影响很小。因此，算法虽然执行了一些操作，但最终结果仍然是原网格，相当于直接返回原网格。