leetcode
leetcode 1201 ~ 1250
二维网格迁移

二维网格迁移

难度:

标签:

题目描述

给你一个 mn 列的二维网格 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

代码结果

运行时间: 27 ms, 内存: 16.6 MB


/*
 * 思路:
 * 1. 使用流将二维数组展平为一维数组。
 * 2. 通过计算迁移次数k得到最终的位置。
 * 3. 使用流将一维数组重新构造成二维数组。
 */
import java.util.Arrays;
import java.util.stream.IntStream;

public class Solution {
    public int[][] shiftGrid(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int[] flat = Arrays.stream(grid).flatMapToInt(Arrays::stream).toArray();
        int[] shifted = new int[m * n];
        IntStream.range(0, m * n).forEach(i -> shifted[(i + k) % (m * n)] = flat[i]);
        return IntStream.range(0, m).mapToObj(i -> Arrays.copyOfRange(shifted, i * n, (i + 1) * n)).toArray(int[][]::new);
    }
}

解释

方法:

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

时间复杂度:

O(m*n)

空间复杂度:

O(m*n)

代码细节讲解

🦆
为什么在移位操作中使用 k mod (m*n) 而不是直接使用 k?假设 k 大于 m*n 会发生什么?
使用 k mod (m*n) 是为了优化性能和避免冗余操作。因为二维网格展平后的一维列表长度为 m*n,当移动次数 k 大于等于 m*n 时,完成一整轮移动后网格会恢复原状,因此只需考虑 k mod (m*n) 余下的移动次数。如果直接使用 k 而 k 大于 m*n,那么很多移动是重复的,没有实际效果,会导致不必要的计算开销。
🦆
在进行列表切片操作时,如何保证切片后的列表元素顺序正确反映了 k 次移动后的网格状态?
列表切片操作通过将原列表分为两部分:最后 k 个元素和前面剩余的元素,然后将这两部分重新连接。具体操作为先取 `-k:`(最后 k 个元素),再取 `:-k`(除最后 k 个元素以外的前面的元素),这样重新组合后的列表正好模拟了元素向右移动 k 位置的结果。这种操作确保了每个元素都正确移动到了应该在的新位置。
🦆
如果输入的网格是空的或者非常小(例如1x1),这个算法是否还有效?
是的,这个算法同样有效,即使对于非常小的网格如 1x1。算法首先将网格转换为一维列表,对于空网格转换结果为空列表,对于 1x1 网格转换结果为单元素列表。在这两种情况下,应用切片操作和重新构造二维网格的过程仍然适用,不会引发任何错误或异常。对于空网格,结果仍然是空;对于 1x1 网格,无论 k 是多少,结果都是原网格,因为只有一个元素,无法实际移动。
🦆
如果 k 为 0,算法会如何处理?会进行不必要的计算还是直接返回原网格?
如果 k 为 0,算法中的 `k %= total_elements` 将导致 k 保持为 0。后续的切片操作 `-k:` 和 `:-k` 将分别解释为整个列表和空列表,所以最终的操作是将整个列表和一个空列表连接,这本质上没有改变列表。虽然技术上进行了一些计算,但这些步骤很简单,对性能影响很小。因此,算法虽然执行了一些操作,但最终结果仍然是原网格,相当于直接返回原网格。

相关问题