题目描述
给你一个 n
行 m
列的二维网格 grid
和一个整数 k
。你需要将 grid
迁移 k
次。
每次 迁移 操作将会引发下述活动:
- 位于
grid[i][j]
的元素将会移动到grid[i][j + 1]
。 - 位于
grid[i][m - 1]
的元素将会移动到grid[i + 1][0]
。 - 位于
grid[n - 1][m - 1]
的元素将会移动到grid[0][0]
。
请你返回 k
次迁移操作后最终得到的 二维网格。
样例
输入:grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出:[[9,1,2],[3,4,5],[6,7,8]]
输入: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]]
输入:grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
输出:[[1,2,3],[4,5,6],[7,8,9]]
限制
1 <= grid.length <= 50
1 <= grid[i].length <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100
算法
(数学,原地算法) $O(nm)$
- 使用额外数组的算法很基础,这里考虑不使用额外数组,且只能遍历一次整个数组。
- 观察从
(0, 0)
位置开始的一次k
迁移,(0, 0)
被换到(0, k)
,依次类推。如果k
和n*m
互质,则所有位置就都换了一次,这样的迁移仅需要常数的空间。 - 如果
k
和n*m
不互质,则除了从(0, 0)
开始后,还需要从(0, 1)
,(0, 2)
等位置开始,一直到(0, g - 1)
的位置开始迁移,其中g
为最大公约数。 - 虽然我们从多个位置开始了迁移,但每个位置的迁移序列都不相同,即每个位置仅会被换一次。
时间复杂度
- 求最大公约数的时间复杂度为 $O(\log (nm))$。
- 每个位置仅会被换一次,故总时间复杂度为 $O(nm)$。
空间复杂度
- 原地算法,只需要常数的额外空间。
C++ 代码
class Solution {
public:
int gcd(int x, int y) {
while (y) {
int t = x % y;
x = y;
y = t;
}
return x;
}
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
int n = grid.size(), m = grid[0].size();
int g = gcd(k, n * m);
for (int s = 0; s < g; s++) {
int x = s / m, y = s % m;
int tmp = grid[x][y];
while (1) {
int nx = x, ny = y - k;
while (ny < 0) {
nx = (nx - 1 + n) % n;
ny += m;
}
grid[x][y] = grid[nx][ny];
if (nx == s / m && ny == s % m) {
grid[x][y] = tmp;
break;
}
x = nx; y = ny;
}
}
return grid;
}
};