How to Rotate a Matrix (Clockwise and Anti-clockwise) in place?
- 时间:2020-10-07 14:14:07
- 分类:网络文摘
- 阅读:94 次
Given a matrix with dimension NxN, rotate the matrix in place the 90 degrees clockwise and anti-clockwise.
For example, original Matrix 3×3:
1 2 3 4 5 | vector<vector<int>> matrix({ {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }); |
vector<vector<int>> matrix({ {1, 2, 3}, {4, 5, 6}, {7, 8, 9} });
Rotating it 90 degree clockwise would make it:
1 2 3 4 5 | vector<vector<int>> matrix({ {7, 4, 1}, {8, 5, 2}, {9, 6, 3} }); |
vector<vector<int>> matrix({ {7, 4, 1}, {8, 5, 2}, {9, 6, 3} });
To solve this problem, the tricks is to use two-step process: First Transpose the matrix (which mirrors by diagonal) Then swap rows or columns by the middle row or middle column.
Transpose a Matrix in-place
Transposing a matrix, we want to swap the matrix[i][j] by matrix[j][i] once. So we can iterate the bottom half or the top half of the matrix.
1 2 3 4 5 6 7 8 9 10 | void transposeMatrix(vector<vector<int>> &matrix) { int N = matrix.size(); if (N == 0) return; assert(matrix[0].size() == N); // make sure it is NxN for (int r = 0; r < N; ++ r) { for (int c = 0; c < r; ++ c) { // bottom half swap(matrix[r][c], matrix[c][r]); } } } |
void transposeMatrix(vector<vector<int>> &matrix) { int N = matrix.size(); if (N == 0) return; assert(matrix[0].size() == N); // make sure it is NxN for (int r = 0; r < N; ++ r) { for (int c = 0; c < r; ++ c) { // bottom half swap(matrix[r][c], matrix[c][r]); } } }
We don’t need to do anything to the elements in the matrix diagonal since it won’t make a difference.
Rotate a Matrix in Place 90 degree clockwise
With the transposed matrix we have the following:
1 2 3 4 5 | vector<vector<int>> matrix({ {1, 4, 7}, {2, 5, 8}, {3, 6, 9} }); |
vector<vector<int>> matrix({ {1, 4, 7}, {2, 5, 8}, {3, 6, 9} });
Now, we can observe that we simply need to swap the colums by the centeral column:
1 2 3 4 5 6 7 8 9 10 11 12 | void rotateClockwise(vector<vector<int>> &matrix) { int N = matrix.size(); if (N == 0) return; assert(matrix[0].size() == N); // make sure it is NxN transposeMatrix(matrix); for (int r = 0; r < N; ++ r) { for (int c = 0; c < N / 2; ++ c) { swap(matrix[r][c], matrix[r][N - c - 1]); } } } |
void rotateClockwise(vector<vector<int>> &matrix) { int N = matrix.size(); if (N == 0) return; assert(matrix[0].size() == N); // make sure it is NxN transposeMatrix(matrix); for (int r = 0; r < N; ++ r) { for (int c = 0; c < N / 2; ++ c) { swap(matrix[r][c], matrix[r][N - c - 1]); } } }
Rotate a Matrix in Place 90 degree Anti-clockwise
Similarly, we can swap the rows in order to make:
1 2 3 4 5 | vector<vector<int>> matrix({ {3, 6, 9}, {2, 5, 8}, {1, 4, 7} }); |
vector<vector<int>> matrix({ {3, 6, 9}, {2, 5, 8}, {1, 4, 7} });
1 2 3 4 5 6 7 8 9 10 11 12 | void rotateAntiClockwise(vector<vector<int>> &matrix) { int N = matrix.size(); if (N == 0) return; assert(matrix[0].size() == N); // make sure it is NxN transposeMatrix(matrix); for (int r = 0; r < N / 2; ++ r) { for (int c = 0; c < M; ++ c) { swap(matrix[r][c], matrix[N - r - 1][c]); } } } |
void rotateAntiClockwise(vector<vector<int>> &matrix) { int N = matrix.size(); if (N == 0) return; assert(matrix[0].size() == N); // make sure it is NxN transposeMatrix(matrix); for (int r = 0; r < N / 2; ++ r) { for (int c = 0; c < M; ++ c) { swap(matrix[r][c], matrix[N - r - 1][c]); } } }
Test Cases for Rotating Matrix
- Empty {{}}
- Single Element
- Identity Matrics
- Sparse Matrics
- Elements in one half (bottom or top)
The time complexity for all above implementations are O(N^2) and the space requirement is O(1) constant since we are doing it in-place without allocating new space.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:那许久未见的人,愿你岁月静好 元旦节游九峰山的作文400字 身边作文1000字 日湖作文300字 书洛阳名园记后原文及翻译 黄冈竹楼记原文及翻译 待漏院记原文及翻译 项羽本纪赞原文及翻译 五帝本纪赞原文及翻译 对楚王问原文及翻译
- 评论列表
-
- 添加评论