循环轮转矩阵
难度:
标签:
题目描述
给你一个大小为 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.lengthn == grid[i].length2 <= m, n <= 50m和n都是 偶数1 <= grid[i][j] <= 50001 <= k <= 109
代码结果
运行时间: 107 ms, 内存: 16.5 MB
/*
* 思路：
* 1. 确定矩阵的层数，使用Stream进行处理。
* 2. 使用Collectors将每一层的元素收集到一个列表中。
* 3. 使用Collections.rotate方法实现旋转。
* 4. 将旋转后的元素放回矩阵中。
*/
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Solution {
public int[][] rotateGrid(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
int layers = Math.min(m, n) / 2;
for (int layer = 0; layer < layers; layer++) {
List<Integer> elements = new ArrayList<>();
int top = layer;
int bottom = m - layer - 1;
int left = layer;
int right = n - layer - 1;
elements.addAll(IntStream.rangeClosed(left, right).mapToObj(i -> grid[top][i]).collect(Collectors.toList()));
elements.addAll(IntStream.rangeClosed(top + 1, bottom).mapToObj(i -> grid[i][right]).collect(Collectors.toList()));
elements.addAll(IntStream.rangeClosed(left, right).mapToObj(i -> grid[bottom][right - i + left]).collect(Collectors.toList()));
elements.addAll(IntStream.rangeClosed(top + 1, bottom - 1).mapToObj(i -> grid[bottom - i + top][left]).collect(Collectors.toList()));
Collections.rotate(elements, k % elements.size());
int index = 0;
for (int i = left; i <= right; i++) grid[top][i] = elements.get(index++);
for (int i = top + 1; i <= bottom; i++) grid[i][right] = elements.get(index++);
for (int i = right - 1; i >= left; i--) grid[bottom][i] = elements.get(index++);
for (int i = bottom - 1; i > top; i--) grid[i][left] = elements.get(index++);
}
return grid;
}
}解释
方法:
该题解采用了层次遍历的方式，按照从外层到内层的顺序，逐层进行旋转操作。对于每一层，首先将该层的元素按照逆时针方向存储到一个临时数组中，然后根据旋转次数k对临时数组进行旋转操作（实际上是将数组分成两部分，然后重新拼接），最后将旋转后的数组元素按照原来的顺序放回到矩阵中。
时间复杂度:
O(m * n)
空间复杂度:
O(min(m, n))
代码细节讲解
🦆
在题解中提到的每一层元素的存储顺序是按照逆时针方向，这种存储方式是否有助于简化旋转操作？如何简化？
▷🦆
题解中的旋转操作是通过数组分割和重新拼接实现的。能否详细解释如何通过计算得到旋转后数组的正确顺序？
▷🦆
旋转操作中，旋转次数k进行了模长操作`k % len(temp)`。这样做的目的是什么？如果不进行模长操作会怎样？
▷