给定一个方阵，将矩阵顺时针旋转 180 度。应该进行改造 到位 在二次时间。
例如，
Input:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Output:
16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Output:
16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1
如果我们以相反的顺序将第一行的元素与最后一行的元素交换，将第二行的元素与倒序的倒数第二行的元素交换，依此类推……我们将得到所需的矩阵。请注意，如果矩阵具有奇数维度，则反转中间行的元素。
该算法可以在 C++、Java 和 Python 中实现如下：
C++
|
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 |
#include <iostream> #include <vector> #include <iomanip> using namespace std; // 原地逆时针旋转矩阵 180 度 void rotateMatrix(vector<vector<int>> &mat) { // `N × N` 矩阵 int N = mat.size(); // 基本情况 if (N == 0) { return; } // 将矩阵旋转 180 度 for (int i = 0; i < N / 2; i++) { for (int j = 0; j < N; j++) { swap(mat[i][j], mat[N - i - 1][N - j - 1]); } } // 处理矩阵具有奇数维度的情况 if (N & 1) { for (int j = 0; j < N/2; j++) { swap(mat[N/2][j], mat[N/2][N - j - 1]); } } } // 打印矩阵的函数 void printMatrix(vector<vector<int>> const &mat) { for (auto &row: mat) { for (auto &i: row) { cout << setw(3) << i; } cout << endl; } cout << endl; } int main() { vector<vector<int>> mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; rotateMatrix(mat); printMatrix(mat); return 0; } |
输出:
16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1
Java
|
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 |
import java.util.Arrays; class Main { // 原地逆时针旋转 180 度 public static void rotateMatrix(int[][] mat) { // 基本情况 if (mat == null || mat.length == 0) { return; } // `N × N` 矩阵 int N = mat.length; // 将矩阵旋转 180 度 for (int i = 0; i < N /2; i++) { for (int j = 0; j < N; j++) { int temp = mat[i][j]; mat[i][j] = mat[N - i - 1][N - j - 1]; mat[N - i - 1][N - j - 1] = temp; } } // 处理矩阵具有奇数维度的情况 if (N % 2 == 1) { for (int j = 0; j < N/2; j++) { int temp = mat[N/2][j]; mat[N/2][j] = mat[N/2][N - j - 1]; mat[N/2][N - j - 1] = temp; } } } public static void main(String[] args) { int[][] mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; rotateMatrix(mat); // 打印矩阵 for (var r: mat) { System.out.println(Arrays.toString(r)); } } } |
输出:
[16, 15, 14, 13]
[12, 11, 10, 9]
[8, 7, 6, 5]
[4, 3, 2, 1]
Python
|
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 |
#就地逆时针旋转180度 def rotateMatrix(mat): # 基础案例 if not mat or not len(mat): return #`N × N`矩阵 N = len(mat) # 将矩阵旋转 180 度 for i in range(N // 2): for j in range(N): temp = mat[i][j] mat[i][j] = mat[N - i - 1][N - j - 1] mat[N - i - 1][N - j - 1] = temp # 处理矩阵具有奇数维的情况 if N % 2 == 1: for j in range(N // 2): temp = mat[N // 2][j] mat[N // 2][j] = mat[N // 2][N - j - 1] mat[N // 2][N - j - 1] = temp if __name__ == '__main__': mat = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16] ] rotateMatrix(mat) #打印矩阵 for r in mat: print(r) |
输出:
[16, 15, 14, 13]
[12, 11, 10, 9]
[8, 7, 6, 5]
[4, 3, 2, 1]
所提出解决方案的时间复杂度为 O(N2) 为 N × N 矩阵并且不需要任何额外的空间。
相关文章：