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) —

推荐阅读:
一道有关比的行程问题  0有哪些含义  这口井有几米深?  拿破仑三角形  求甲乙两车的速度  获纪念奖的有多少人?  程大位与剩余定理  “位数”和“数位”的意义为什么不同?  节约用水的资料  求发芽率、合格率、出粉率等百分率的公式中为什么都要乘100%? 
评论列表
添加评论