# 將矩陣旋轉 90 度，而無需使用任何額外空間| 系列 2 > 原文： [https://www.geeksforgeeks.org/rotate-matrix-90-degree-without-using-extra-space-set-2/](https://www.geeksforgeeks.org/rotate-matrix-90-degree-without-using-extra-space-set-2/) 給定一個正方形矩陣，將其沿逆時針方向旋轉 90 度，而無需使用任何額外空間。 **示例**： ``` Input: 1 2 3 4 5 6 7 8 9 Output: 3 6 9 2 5 8 1 4 7 Rotated the input matrix by 90 degrees in anti-clockwise direction. Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13 Rotated the input matrix by 90 degrees in anti-clockwise direction. ``` 在另一篇文章中已經討論了需要額外空間的方法： [原位旋轉方陣 90 度| 系列 1](https://www.geeksforgeeks.org/inplace-rotate-square-matrix-by-90-degrees/) **這篇文章以空間優化的不同方法討論了相同的問題。** **方法**：的想法是找到矩陣的轉置，然后反轉轉置矩陣的列。 *這是顯示其工作原理的示例。*  **算法**： 1. 為了解決給定的問題，有兩個任務。 第一個是找到轉置，第二個是在不使用多余空間的情況下反轉列 2. 矩陣的轉置是指矩陣在對角線上翻轉時，即元素的行索引變為列索引，反之亦然。 因此，要找到轉置處，將（i，j）處的元素與（j，i）進行互換。 運行兩個循環，外循環從 0 到行數，內循環從 0 到外循環的索引。 3. 要反轉轉置矩陣的列，請運行兩個嵌套循環，外循環從 0 到列數，內循環從 0 到行數/ 2，將（i，j）的元素與（i，row [count-1 -j]），其中 i 和 j 分別是內循環和外循環的索引。 ## C++ ```cpp // C++ program for left // rotation of matrix by 90 degree // without using extra space #include <bits/stdc++.h> using namespace std; #define R 4 #define C 4 // After transpose we swap // elements of column // one by one for finding left // rotation of matrix // by 90 degree void reverseColumns(int arr[R][C]) { ????for (int i = 0; i < C; i++) ????????for (int j = 0, k = C - 1; ?????????????j < k; j++, k--) ????????????swap( ????????????????arr[j][i], arr[k][i]); } // Function for do transpose of matrix void transpose(int arr[R][C]) { ????for (int i = 0; i < R; i++) ????????for (int j = i; j < C; j++) ????????????swap(arr[i][j], arr[j][i]); } // Function for print matrix void printMatrix(int arr[R][C]) { ????for (int i = 0; i < R; i++) { ????????for (int j = 0; j < C; j++) ????????????cout << arr[i][j] << " "; ????????cout << '\n'; ????} } // Function to anticlockwise // rotate matrix by 90 degree void rotate90(int arr[R][C]) { ????transpose(arr); ????reverseColumns(arr); } // Driven code int main() { ????int arr[R][C] = { { 1, 2, 3, 4 }, ??????????????????????{ 5, 6, 7, 8 }, ??????????????????????{ 9, 10, 11, 12 }, ??????????????????????{ 13, 14, 15, 16 } }; ????rotate90(arr); ????printMatrix(arr); ????return 0; } ``` ## Java ```java // JAVA Code for left Rotation of a // matrix by 90 degree without using // any extra space import java.util.*; class GFG { ????// After transpose we swap elements of ????// column one by one for finding left ????// rotation of matrix by 90 degree ????static void reverseColumns(int arr[][]) ????{ ????????for (int i = 0; i < arr[0].length; i++) ????????????for (int j = 0, k = arr[0].length - 1; ?????????????????j < k; j++, k--) { ????????????????int temp = arr[j][i]; ????????????????arr[j][i] = arr[k][i]; ????????????????arr[k][i] = temp; ????????????} ????} ????// Function for do transpose of matrix ????static void transpose(int arr[][]) ????{ ????????for (int i = 0; i < arr.length; i++) ????????????for (int j = i; j < arr[0].length; ?????????????????j++) { ????????????????int temp = arr[j][i]; ????????????????arr[j][i] = arr[i][j]; ????????????????arr[i][j] = temp; ????????????} ????} ????// Function for print matrix ????static void printMatrix(int arr[][]) ????{ ????????for (int i = 0; i < arr.length; i++) { ????????????for (int j = 0; j < arr[0].length; ?????????????????j++) ????????????????System.out.print(arr[i][j] + " "); ????????????System.out.println(""); ????????} ????} ????// Function to anticlockwise rotate ????// matrix by 90 degree ????static void rotate90(int arr[][]) ????{ ????????transpose(arr); ????????reverseColumns(arr); ????} ????/* Driver program to test above function */ ????public static void main(String[] args) ????{ ????????int arr[][] = { { 1, 2, 3, 4 }, ????????????????????????{ 5, 6, 7, 8 }, ????????????????????????{ 9, 10, 11, 12 }, ????????????????????????{ 13, 14, 15, 16 } }; ????????rotate90(arr); ????????printMatrix(arr); ????} } // This code is contributed by Arnav Kr. Mandal. ``` ## C# ```cs // C# program for left rotation // of matrix by 90 degree // without using extra space using System; class GFG { ????static int R = 4; ????static int C = 4; ????// After transpose we swap ????// elements of column one ????// by one for finding left ????// rotation of matrix by ????// 90 degree ????static void reverseColumns(int[, ] arr) ????{ ????????for (int i = 0; i < C; i++) ????????????for (int j = 0, k = C - 1; ?????????????????j < k; j++, k--) { ????????????????int temp = arr[j, i]; ????????????????arr[j, i] = arr[k, i]; ????????????????arr[k, i] = temp; ????????????} ????} ????// Function for do ????// transpose of matrix ????static void transpose(int[, ] arr) ????{ ????????for (int i = 0; i < R; i++) ????????????for (int j = i; j < C; j++) { ????????????????int temp = arr[j, i]; ????????????????arr[j, i] = arr[i, j]; ????????????????arr[i, j] = temp; ????????????} ????} ????// Function for print matrix ????static void printMatrix(int[, ] arr) ????{ ????????for (int i = 0; i < R; i++) { ????????????for (int j = 0; j < C; j++) ????????????????Console.Write(arr[i, j] + " "); ????????????Console.WriteLine(""); ????????} ????} ????// Function to anticlockwise ????// rotate matrix by 90 degree ????static void rotate90(int[, ] arr) ????{ ????????transpose(arr); ????????reverseColumns(arr); ????} ????// Driver code ????static void Main() ????{ ????????int[, ] arr = { { 1, 2, 3, 4 }, ????????????????????????{ 5, 6, 7, 8 }, ????????????????????????{ 9, 10, 11, 12 }, ????????????????????????{ 13, 14, 15, 16 } }; ????????rotate90(arr); ????????printMatrix(arr); ????} ????// This code is contributed ????// by Sam007 } ``` ## Python 3 ``` # Python 3 program for left rotation of matrix by 90 # degree without using extra space R = 4 C = 4 # After transpose we swap elements of column # one by one for finding left rotation of matrix # by 90 degree def reverseColumns(arr): ????for i in range(C): ????????j = 0 ????????k = C-1 ????????while j < k: ????????????t = arr[j][i] ????????????arr[j][i] = arr[k][i] ????????????arr[k][i] = t ????????????j += 1 ????????????k -= 1 # Function for do transpose of matrix def transpose(arr): ????for i in range(R): ????????for j in range(i, C): ????????????t = arr[i][j] ????????????arr[i][j] = arr[j][i] ????????????arr[j][i] = t # Function for print matrix def printMatrix(arr): ????for i in range(R): ????????for j in range(C): ????????????print(str(arr[i][j]), end =" ") ????????print() # Function to anticlockwise rotate matrix # by 90 degree def rotate90(arr): ????transpose(arr) ????reverseColumns(arr) # Driven code arr = [[1, 2, 3, 4], ????????[5, 6, 7, 8], ????????[9, 10, 11, 12], ????????[13, 14, 15, 16] ????]; rotate90(arr) printMatrix(arr) ``` ## PHP ```php <?php // PHP program for left rotation of matrix by 90 $R = 4; $C = 4; // Function to rotate the matrix by 90 degree function reverseColumns(&$arr) { ????global $C; ????for ($i = 0; $i < $C; $i++) ????{ ????????for ($j = 0, $k = $C - 1; $j < $k; $j++, $k--) ????????{ ????????????$t = $arr[$j][$i]; ????????????$arr[$j][$i] = $arr[$k][$i]; ????????????$arr[$k][$i] = $t; ????????} ????}??????? } // Function for transpose of matrix function transpose(&$arr) { ????global $R, $C; ????for ($i = 0; $i < $R; $i++) ????{ ????????for ($j = $i; $j < $C; $j++) ????????{ ????????????$t = $arr[$i][$j]; ????????????$arr[$i][$j] = $arr[$j][$i]; ????????????$arr[$j][$i] = $t; ????????} ????} } // Function for display the matrix function printMatrix(&$arr) { ????global $R, $C; ????for ($i = 0; $i < $R; $i++) { ????????for ($j = 0; $j < $C; $j++) ????????????echo $arr[$i][$j]." "; ????????echo "\n"; ????} } // Function to anticlockwise rotate matrix // by 90 degree function rotate90(&$arr) { ????transpose($arr); ????reverseColumns($arr); } // Driven code $arr = array( array( 1, 2, 3, 4 ), ?????????????????array( 5, 6, 7, 8 ), ?????????????????array( 9, 10, 11, 12 ), ?????????????????array( 13, 14, 15, 16 ) ); rotate90($arr); printMatrix($arr); return 0; ?> ``` **輸出**： ``` 4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13 ``` **復雜度分析**： * **時間復雜度**： O（R * C）。 矩陣被遍歷兩次，所以復雜度為 O（R * C）。 * **空間復雜度**：`O(1)`。 由于不需要額外的空間，因此空間復雜度是恒定的。 **實現**：讓我們看看 [Python numpy](https://www.geeksforgeeks.org/python-numpy/) 的一種方法，可用于得出特定的解決方案。 ``` # Alternative implementation using numpy import numpy # Driven code? arr = [[1, 2, 3, 4],? ????????[5, 6, 7, 8],? ????????[9, 10, 11, 12],? ????????[13, 14, 15, 16]? ????];? # Define flip algorith (Note numpy.flip is a builtin f # unction for versions > v.1.12.0) def flip(m, axis): ????if not hasattr(m, 'ndim'): ????????m = asarray(m) ????indexer = [slice(None)] * m.ndim ????try: ????????indexer[axis] = slice(None, None, -1) ????except IndexError: ????????raise ValueError("axis =% i is invalid for the % i-dimensional input array" ?????????????????????????% (axis, m.ndim)) ????return m[tuple(indexer)] # Transpose the matrix trans = numpy.transpose(arr) # Flip the matrix anti-clockwise (1 for clockwise) flipmat = flip(trans, 0) print("\nnumpy implementation\n") print(flipmat) ``` **輸出**： ``` numpy implementation [[ 4 8 12 16] [ 3 7 11 15] [ 2 6 10 14] [ 1 5 9 13]] ``` **注意**：上述步驟/程序向左（或逆時針）旋轉。 讓我們看看如何進行右旋轉或順時針旋轉。 該方法將是相似的。 找到矩陣的轉置，然后反轉轉置矩陣的行。 *這是完成的方式。*  本文由 [DANISH_RAZA](https://www.facebook.com/danish.raza.98096721) 提供。 如果您喜歡 GeeksforGeeks 并希望做出貢獻，則也可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。 查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。