在 C++ 中旋轉矩陣 90 度,不使用任何額外空間


我們得到一個二維陣列,它將用於形成矩陣模式。任務是將矩陣逆時針旋轉 90 度,使第一行成為第一列,第二行成為第二列,第三行成為第三列,挑戰在於我們不必使用任何額外空間。

讓我們看看這個各種輸入輸出場景:

輸入

int arr[row_col_size][row_col_size] = { { 5, 1, 4},
   { 9, 16, 12 },
   { 2, 8, 9}}

輸出

Rotation of a matrix by 90 degree without using any extra space is:
4 12 9
1 16 8
5 9  2

解釋:我們得到一個整數型別的二維陣列。現在我們將矩陣順時針旋轉 90 度。

Before rotation-:
{ { 5, 1, 4},
{ 9, 16, 12 },
{ 2, 8, 9}}
After rotation-:
2 12 9
1 16 8
5 9  2

輸入

int arr[row_col_size][row_col_size] = { { 2, 1, 9},
   { 11, 6, 32 },
   { 3, 7, 5}}

輸出

Rotation of a matrix by 90 degree in clockwise direction without using any extra space is:
9 32 5
1 6  7
2 7  3

解釋:我們得到一個整數型別的二維陣列。現在我們將矩陣順時針旋轉 90 度。

Before rotation-:
{ { 2, 1, 9},
{ 11, 6, 32 },
{ 3, 7, 5}}
After rotation-:
9 32 5
1 6  7
2 7  3

下面程式中使用的方法如下:

1. 樸素方法

  • 輸入一個將被視為具有 row_col_size 行列的矩陣的二維整數陣列。

  • 將資料傳遞給函式 Rotate_ClockWise(arr)。

  • 在函式 Rotate_ClockWise(arr) 內部:

    • 從 i = 0 開始迴圈,直到 i 小於 row_col_size/2。

    • 在迴圈內,從 j = 0 開始另一個迴圈,直到 j 小於 row_col_size - i - 1。

    • 在迴圈內,設定 ptr 為 arr[i][j],arr[i][j] 為 arr[row_col_size - 1 - j][i],arr[row_col_size - 1 - j][i] 為 arr[row_col_size - 1 - i][row_col_size - 1 - j],arr[row_col_size - 1 - i][row_col_size - 1 - j] 為 arr[j][row_col_size - 1 - i],arr[j][row_col_size - 1 - i] 為 ptr。

  • 從 i = 0 開始迴圈,直到 i 小於 row_col_size。在迴圈內,從 j = 0 開始另一個迴圈,直到 j 小於 row_col_size;j++ 並列印 arr[i][j]。

2. 高效方法

  • 輸入一個將被視為具有 row_col_size 行列的矩陣的二維整數陣列。

  • 將資料傳遞給函式 Rotate_ClockWise(arr)。

  • 在函式 Rotate_ClockWise(arr) 內部:

    • 從 i = 0 開始迴圈,直到 i 小於 row_col_size。

    • 在迴圈內,從 j = 0 開始另一個迴圈,直到 j 小於 row_col_size - i。

    • 在迴圈內,設定 ptr 為 arr[i][j],arr[i][j] 為 arr[row_col_size - 1 - j]arr[row_col_size - 1 - i],[row_col_size - 1 - j] 為 arr[j][row_col_size - 1 - i] 為 ptr。

    • 從 i = 0 開始迴圈,直到 i 小於 row_col_size / 2。在迴圈內,從 j = 0 開始另一個迴圈,直到 j 小於 row_col_size。在迴圈內,設定 ptr 為 arr[i][j],arr[i][j] 為 arr[row_col_size - 1 - i][j],arr[row_col_size - 1 - i][j] 為 ptr。

  • 從 i = 0 開始迴圈,直到 i 小於 row_col_size。在迴圈內,從 j = 0 開始另一個迴圈,直到 j 小於 row_col_size;j++ 並列印 arr[i][j]。

樸素方法

示例

#include <bits/stdc++.h>
using namespace std;
#define row_col_size 3
void Rotate_ClockWise(int arr[row_col_size][row_col_size]){
   for(int i = 0; i < row_col_size / 2; i++){
      for(int j = i; j < row_col_size - i - 1; j++){
         int ptr = arr[i][j];
         arr[i][j] = arr[row_col_size - 1 - j][i];
         arr[row_col_size - 1 - j][i] = arr[row_col_size - 1 - i][row_col_size - 1 - j];
         arr[row_col_size - 1 - i][row_col_size - 1 - j] = arr[j][row_col_size - 1 - i];
         arr[j][row_col_size - 1 - i] = ptr;
      }
   }
}
int main(){
   int arr[row_col_size][row_col_size] = { { 5, 1, 4},{ 9, 16, 12 },{ 2, 8, 9}};
   Rotate_ClockWise(arr);
   cout<<"Rotation of a matrix by 90 degree in clockwise direction without using any extra space is: \n";
   for(int i = 0; i < row_col_size; i++){
      for(int j = 0; j < row_col_size; j++){
         cout << arr[i][j] << " ";
      }
      cout << '\n';
   }
   return 0;
}

輸出

如果我們執行上面的程式碼,它將生成以下輸出:

Rotation of a matrix by 90 degree in clockwise direction without using any extra space is:
2 9  5
8 16 1
9 12 4

高效方法

示例

#include <bits/stdc++.h>
using namespace std;
#define row_col_size 3
void Rotate_ClockWise(int arr[row_col_size][row_col_size]){
   for(int i = 0; i < row_col_size; i++){
      for(int j = 0; j < row_col_size - i; j++){
         int ptr = arr[i][j];
         arr[i][j] = arr[row_col_size - 1 - j][row_col_size - 1 - i];
         arr[row_col_size - 1 - j][row_col_size - 1 - i] = ptr;
      }
   }
   for(int i = 0; i < row_col_size / 2; i++){
      for(int j = 0; j < row_col_size; j++){
         int ptr = arr[i][j];
         arr[i][j] = arr[row_col_size - 1 - i][j];
         arr[row_col_size - 1 - i][j] = ptr;
      }
   }
}
int main(){
   int arr[row_col_size][row_col_size] = { { 5, 1, 4},{ 9, 16, 12 },{ 2, 8, 9}};
   Rotate_ClockWise(arr);
   cout<<"Rotation of a matrix by 90 degree in clockwise direction without using any extra space is: \n";
   for(int i = 0; i < row_col_size; i++){
      for(int j = 0; j < row_col_size; j++){
         cout << arr[i][j] << " ";
      }
      cout << '\n';
   }
   return 0;
}

輸出

如果我們執行上面的程式碼,它將生成以下輸出:

Rotation of a matrix by 90 degree in clockwise direction without using any extra space is:
2 9  5
8 16 1
9 12 4

更新於:2021-11-03

429 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始
廣告