如何将 N x N 矩阵旋转90度，且需要原地完成？
如何将一个 N x N 的矩阵旋转90度？
26
- Passionate programmer
8
1重复的问题：如何旋转二维数组？（这些解决方案中的代码大多不是C++，但算法足够简单，以至于在大多数情况下将其转换为C++应该是微不足道的） - James McNellis
3这取决于矩阵在你的数据结构中是如何存储的。你到目前为止尝试过什么？ - Greg Hewgill
请顺时针旋转，确保不要创建额外的矩阵。 - Passionate programmer
@James，你链接的问题并不要求旋转是原地进行的，也没有任何答案提出这样的解决方案。 - P Shved
最近我看到了很多关于旋转的问题，但确切地说矩阵旋转是什么意思就更加困难了。 - nikhil
显示剩余3条评论
5个回答
57
for(int i=0; i<n/2; i++)
for(int j=0; j<(n+1)/2; j++)
cyclic_roll(m[i][j], m[n-1-j][i], m[n-1-i][n-1-j], m[j][n-1-i]);
void cyclic_roll(int &a, int &b, int &c, int &d)
{
int temp = a;
a = b;
b = c;
c = d;
d = temp;
}
注意 我没有测试过这个代码，只是现场编写的。在实际使用前，请务必进行测试。
- Pavel Radzivilovsky
6
你能解释一下你是如何得出这些索引的吗？ - Passionate programmer
4解释指数... 想象一下当旋转90度时，位置(i,j)会转移到哪里。只需想象图片即可。(i,j)->(end-j, i)。与原始矩阵从左侧的距离越远，它就距离矩阵底部越远。 - Pavel Radzivilovsky
2如果逆时针旋转，则映射为 a[p][k] --> a[N-1-k][p] --> a[N-1-p][N-1-k] --> a[k][N-1-p]。我认为 i 的约束条件也存在错误。在 for 循环中应该是 i < n/2（对于 j 来说没问题）。看下面的3x3示例。当旋转2时，数字4就被处理了。您不希望再次在 i = 1 和 j = 0 时进行旋转。 - Maciej Hehl
4我无法编辑。代码应该是：
for(int i=0; i < N/2; i++)
for(int j=0; j < (N+1)/2; j++)
对 a[i][j]，a[N-1-j][i]，a[N-1-i][N-1-j]，a[j][N-1-i] 进行循环滚动操作(cyclic_roll)。 - Maciej Hehl
2cyclic_roll函数的第三个参数仍需要更正。应该是a [n-1-i] [n-1-j] :) - Maciej Hehl
1好的，Pavel... 你逆时针旋转，对吧？我认为OP要求顺时针旋转，所以我想指出看到这个答案的人应该记住这一点，不要盲目地复制和粘贴 :). - Kiril
11
这是我的解决方案： (顺时针旋转90度)
对数组进行转置（类似于矩阵转置）
反转每一行的元素
cons int row = 10;
cons int col = 10;
//transpose
for(int r = 0; r < row; r++) {
for(int c = r; c < col; c++) {
swap(Array[r][c], Array[c][r]);
}
}
//reverse elements on row order
for(int r = 0; r < row; r++) {
for(int c =0; c < col/2; c++) {
swap(Array[r][c], Array[r][col-c-1])
}
}
如果逆时针旋转π/2
转置数组
反转列顺序的元素
不要测试代码！ 欢迎任何建议！
- elliptic00
3
1每个元素将被移动两次（与@Pavel Radzivilovsky的答案相比为1.25倍），因此效率较低。 “好处”是由于不需要“int temp”，内存需求减少了四个字节... - Jean-François Corbett
2同@Jean-FrançoisCorbett所说，这个答案不如其他答案高效。但是，这个答案肯定更简单。实际上，我也实现了相同的算法！！ - MalTec
1非常感谢，这大大简化了解决方案。 - Validus Oculus
0
//Java version, fully tested
public class Rotate90degree {
public static void reverseElementsRowWise(int[][] matrix) {
int n = matrix.length;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n / 2; ++j) {
int temp = matrix[i][n - j - 1];
matrix[i][n - j - 1] = matrix[i][j];
matrix[i][j] = temp;
}
}
}
public static void transpose(int[][] matrix) {
int n = matrix.length;
for(int i = 0; i < n; ++i) {
for(int j = i + 1; j < n; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
public static void rotate90(int[][] matrix) {
transpose(matrix);
reverseElementsRowWise(matrix);
}
public static void print(int[][] matrix) {
int n = matrix.length;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
System.out.print(matrix[i][j]);
System.out.print(' ');
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
System.out.println("before");
print(matrix);
rotate90(matrix);
System.out.println("after");
print(matrix);
}
}
- Jiaji Li
0
一个完整的C程序，展示了我的方法。本质上它是递归算法。在每次递归时旋转外层。当矩阵变成1x1或0x0时停止。
#include <stdio.h>
int matrix[4][4] = {
{11, 12, 13, 14},
{21, 22, 23, 24},
{31, 32, 33, 34},
{41, 42, 43, 44}
};
void print_matrix(int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf(" %d ", matrix[i][j]);
}
printf("\n");
}
}
int *get(int offset, int x, int y)
{
return &matrix[offset + x][offset + y];
}
void transpose(int offset, int n)
{
if (n > 1) {
for (int i = 0; i < n - 1; i++) {
int *val1 = get(offset, 0, i);
int *val2 = get(offset, i, n - 1);
int *val3 = get(offset, n - 1, n - 1 - i);
int *val4 = get(offset, n - 1 - i, 0);
int temp = *val1;
*val1 = *val4;
*val4 = *val3;
*val3 = *val2;
*val2 = temp;
}
transpose(offset + 1, n - 2);
}
}
main(int argc, char *argv[])
{
print_matrix(4);
transpose(0, 4);
print_matrix(4);
return 0;
}
- Chetan Narsude
-5
你可以创建第二个数组，然后通过在第一个数组中按行主序读取并在第二个数组中按列主序写入来将第一个数组复制到第二个数组中。
因此，你需要复制：
1 2 3
4 5 6
7 8 9
而你需要读取第一行，然后从那里开始向上写：
3
2
1
- samoz
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接