二维网格迁移
难度:
标签:
题目描述
给你一个 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
代码结果
运行时间: 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 次移动后的网格状态?
▷🦆
如果输入的网格是空的或者非常小(例如1x1),这个算法是否还有效?
▷🦆
如果 k 为 0,算法会如何处理?会进行不必要的计算还是直接返回原网格?
▷