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

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

2022-05-14 14:05:14【51CTO】


题目

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

边栏推荐

猜你喜欢

随机推荐