将矩阵旋转 90 度，而无需使用任何额外空间| 系列 2 · GeeksForGeeks 中文系列教程

# 将矩阵旋转 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/) **这篇文章以空间优化的不同方法讨论了相同的问题。** **方法**：的想法是找到矩阵的转置，然后反转转置矩阵的列。 *这是显示其工作原理的示例。* ![](https://img.kancloud.cn/75/46/7546118ebcc0542ee73754eee5b1256a_1281x369.png) **算法**： 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]] ``` **注意**：上述步骤/程序向左（或逆时针）旋转。让我们看看如何进行右旋转或顺时针旋转。该方法将是相似的。找到矩阵的转置，然后反转转置矩阵的行。 *这是完成的方式。* ![](https://img.kancloud.cn/d5/66/d56612bb21fdd8b27aab00ab65e49fb7_1281x369.png) 本文由 [DANISH_RAZA](https://www.facebook.com/danish.raza.98096721) 提供。如果您喜欢 GeeksforGeeks 并希望做出贡献，则也可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰写文章，或将您的文章邮寄至 tribution@geeksforgeeks.org。查看您的文章出现在 GeeksforGeeks 主页上，并帮助其他 Geeks。