C++程序 旋转矩阵元素
给定一个矩阵,以顺时针方向旋转矩阵元素。
例子:
输入:
1 2 3
4 5 6
7 8 9
输出:
4 1 2
7 5 3
8 9 6
对于4*4矩阵:
输入:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
输出:
5 1 2 3
9 10 6 4
13 11 7 8
14 15 16 12
思路是使用类似于螺旋形式打印矩阵的程序的循环。一个接一个地旋转所有的环,从最外层开始。要旋转一个环,需要进行以下操作。
1)移动顶部行的元素。
2)移动最后一列的元素。
3)移动底部行的元素。
4)移动第一列的元素。
只要内部环还存在,就重复上述步骤。
下面实现了上述思想。
// C++ program to rotate a matrix
#include <iostream>
#define R 4
#define C 4
using namespace std;
// A function to rotate a matrix
// mat[][] of size R x C.
// Initially, m = R and n = C
void rotatematrix(int m, int n,
int mat[R][C])
{
int row = 0, col = 0;
int prev, curr;
/* row - Starting row index
m - ending row index
col - starting column index
n - ending column index
i - iterator */
while (row < m && col < n)
{
if (row + 1 == m ||
col + 1 == n)
break;
// Store the first element of
// next row, this element will
// replace first element of current
// row
prev = mat[row + 1][col];
/* Move elements of first row from
the remaining rows */
for (int i = col; i < n; i++)
{
curr = mat[row][i];
mat[row][i] = prev;
prev = curr;
}
row++;
/* Move elements of last column
from the remaining columns */
for (int i = row; i < m; i++)
{
curr = mat[i][n-1];
mat[i][n-1] = prev;
prev = curr;
}
n--;
/* Move elements of last row from
the remaining rows */
if (row < m)
{
for (int i = n-1; i >= col; i--)
{
curr = mat[m-1][i];
mat[m-1][i] = prev;
prev = curr;
}
}
m--;
/* Move elements of first column from
the remaining行 */
if (col < n)
{
for (int i = m-1; i >= row; i--)
{
curr = mat[i][col];
mat[i][col] = prev;
prev = curr;
}
}
col++;
}
// 打印旋转后的矩阵
for (int i=0; i<R; i++)
{
for (int j=0; j<C; j++)
cout << mat[i][j] << " ";
cout << endl;
}
}
// 主函数
int main()
{
// 测试用例1
int a[R][C] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
// 测试用例2
/* int a[R][C] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
*/ rotatematrix(R, C, a);
return 0;
}
输出:
5 1 2 3
9 10 6 4
13 11 7 8
14 15 16 12
时间复杂度: O(max(m,n) * max(m,n))
辅助空间: O(m*n)