当前位置:网站首页>经典算法面试题目-矩阵旋转90度(1.6)

经典算法面试题目-矩阵旋转90度(1.6)

2022-05-14 14:05:1451CTO


题目

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

一张图像表示成NxN的矩阵,图像中每个像素是4个字节,写一个函数把图像旋转90度。 你能原地进行操作吗?(即不开辟额外的存储空间)

解答

我们假设要将图像逆时针旋转90度,顺时针是一个道理。如果原图如下所示:

      
      
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
  • 1.
  • 2.
  • 3.
  • 4.

那么逆时针旋转90度后的图应该是:

      
      
4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13
  • 1.
  • 2.
  • 3.
  • 4.

我们要如何原地进行操作以达到上面的效果呢?可以分两步走。 第一步交换主对角线两侧的对称元素,第二步交换第i行和第n-1-i行,即得到结果。 看图示:(如果是顺时针, 第一步交换/对角线两侧的对称元素,第二步交换第i行和第n-1-i行,即得到结果。)

      
      
原图: 第一步操作后: 第二步操作后:
1 2 3 4 1 5 9 13 4 8 12 16
5 6 7 8 2 6 10 14 3 7 11 15
9 10 11 12 3 7 11 15 2 6 10 14
13 14 15 16 4 8 12 16 1 5 9 13
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.

顺时针90度与逆时针90度的代码如下:

      
      
#include <iostream>
using namespace std;

void swap(int *a, int *b){
int t = *a;
*a = *b;
*b = t;
}
//这2个交换函数,选一个就行了,我只是为了演示它们实现的结果是一样
void swap2(int &a,int &b){
int t = a;
a = b;
b = t;
}


//顺时针
void clockwise(int a[][4],int n){
for(int i=0; i<n; ++i)
for(int j=0; j<n-i; ++j)
swap(a[i][j], a[n-1-j][n-1-i]);

for(int i=0; i<n/2; ++i)
for(int j=0; j<n; ++j)
swap(a[i][j], a[n-1-i][j]);
}

//逆时针
void transpose(int a[][4], int n){
for(int i=0; i<n; ++i)
for(int j=i+1; j<n; ++j)
swap(&a[i][j], &a[j][i]);
for(int i=0; i<n/2; ++i)
for(int j=0; j<n; ++j)
swap(&a[i][j], &a[n-1-i][j]);
}
int main(){
int a[4][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
};
for(int i=0; i<4; ++i){
for(int j=0; j<4; ++j)
cout<<a[i][j]<<" ";
cout<<endl;
}
cout<<endl;
transpose(a, 4);
cout<<"逆时针转90度"<<endl;
for(int i=0; i<4; ++i){
for(int j=0; j<4; ++j)
cout<<a[i][j]<<" ";
cout<<endl;
}
cout<<endl;
a = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
};
for(int i=0; i<4; ++i){
for(int j=0; j<4; ++j)
cout<<a[i][j]<<" ";
cout<<endl;
}
clockwise(a,4);
cout<<endl;
cout<<"顺时针转90度"<<endl;
for(int i=0; i<4; ++i){
for(int j=0; j<4; ++j)
cout<<a[i][j]<<" ";
cout<<endl;
}
return 0;
}
  • 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.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
  • 69.
  • 70.
  • 71.
  • 72.
  • 73.
  • 74.
  • 75.
  • 76.
  • 77.
  • 78.

输出结果:

经典算法面试题目-矩阵旋转90度(1.6)_算法



原网站

版权声明
本文为[51CTO]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_14290964/5293025

随机推荐