C++程序 将矩阵对角线以外的元素沿顺时针方向旋转90度K次
给定一个方阵 mat[][] ,其维度为 N ,以及一个整数 K ,任务是将矩阵沿顺时针方向旋转 K 次,而不改变对角线元素的位置。
示例:
输入: mat[][] = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}, {21, 22, 23, 24, 25}},K = 1
输出:
1 16 11 6 5
22 7 12 9 2
23 18 13 8 3
24 17 14 19 4
21 20 15 10 25
输入: mat[][] = {{10, 11}, {12, 13}}, K = 2
输出:
10 11
12 13
方法: 可以使用本文中讨论的想法和矩阵顺时针旋转4次后恢复的事实来解决给定问题。按照下面的步骤解决给定的问题:
- 更新 K 的值为 K % 4 。
- 循环,直到 K 为正,并执行以下步骤:
- 遍历矩阵,在 i 的范围为 [0, N / 2) ,而 j 的范围为 [0, N – i – 1) ,并执行以下步骤:
- 如果 i != j 且 (i + j) != (N – 1) 的值,则执行以下步骤:
- 将
mat[i][j]
的值存储在临时变量 temp 中。 - 更新
mat[i][j]
的值为mat[N – 1 – j][i]
。 - 更新
mat[N – 1 – j][i]
的值为mat[N – 1 -i][N – 1 – j]
。 - 更新
mat[N – 1 – i][N – 1 – j]
的值为mat[j][N – 1 – i]
。 - 更新
mat[j][N – 1 – i]
的值为 temp 。
- 将
- 完成上述步骤后,打印已更新的矩阵。
下面是上述方法的实现代码:
// C++程序的上述方法
#include <bits/stdc++.h>
using namespace std;
// 打印矩阵的函数
void print(vector<vector<int> >& mat)
{
// 遍历每一行
for (int i = 0; i < mat.size(); i++) {
// 遍历每一列
for (int j = 0; j < mat[0].size(); j++)
// 打印值
cout << setw(3) << mat[i][j];
cout << "
";
}
}
// 执行顺时针交换矩阵元素的函数
void performSwap(vector<vector<int> >& mat,
int i, int j)
{
int N = mat.size();
// 存储最后一行
int ei = N - 1 - i;
// 存储最后一列
int ej = N - 1 - j;
// 执行交换
int temp = mat[i][j];
mat[i][j] = mat[ej][i];
mat[ej][i] = mat[ei][ej];
mat[ei][ej] = mat[j][ei];
mat[j][ei] = temp;
}
// 将矩阵的非对角元素顺时针旋转K次的函数
void rotate(vector<vector<int> >& mat,
int N, int K)
{
// 将K更新为K%4
K = K % 4;
// 当K为正数时遍历
while (K--) {
// 每行遍历到N/2
for (int i = 0; i < N / 2; i++) {
// 遍历每一列从i到N-i-1
for (int j = i;
j < N - i - 1; j++) {
// 检查是否在i,j处的元素不是对角线元素
if (i != j
&& (i + j) != N - 1) {
// 执行交换
performSwap(mat, i, j);
}
}
}
}
// 打印矩阵
print(mat);
}
// 驱动程序
int main()
{
int K = 5;
vector<vector<int> > mat = {
{ 1, 2, 3, 4 },
{ 6, 7, 8, 9 },
{ 11, 12, 13, 14 },
{ 16, 17, 18, 19 },
};
int N = mat.size();
rotate(mat, N, K);
return 0;
}
输出:
1 11 6 4
17 7 8 2
18 12 13 3
16 14 9 19
时间复杂度: O(N 2 )
辅助空间: O(1)