在 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