n*n矩阵旋转
题目描述
对一个n*n矩阵中的元素进行顺时针90度旋转，要求不得new新矩阵，必须原地操作。
题解
方法一
先分析矩阵中的元素$a_{i,j}$(假设左上角元素为$a_{0,0}$)顺时针旋转之后到了新矩阵的哪个位置：
由于顺时针旋转后，$a_{i,j}$会从第j列旋转到第j行，$a_{i,j}$从第i行旋转到倒数第i列，所以顺时针旋转90度会将$a_{i,j}$变换到$a_{j,n-1-i}$的位置上去。
接下来是分析如何枚举矩阵的元素，进行这种旋转操作，这是面试时我没有想出来的。
这个方法一的枚举方案就是将整个大矩阵M划分为四个小矩阵$A_{0,0}$，$A_{0,1}$，$A_{1,0}$，$A_{1,1}$，对大矩阵M的旋转90度操作就是将$A_{0,0}$旋转到了$A_{0,1}$的位置，$A_{0,1}$旋转到$A_{1,1}$的位置，$A_{1,1}$旋转到$A_{1,0}$的位置，$A_{1,0}$旋转到$A_{0,0}$的位置。所以需要做的就是枚举左上角小矩阵$A_{0,0}$中的元素$a_{i,j}$即可。对每个$A_{0,0}$中的$a_{i,j}$(这个坐标仍然是大矩阵M中的坐标)，将其旋转到$A_{0,1}$中的$a_{j,n-1-i}$，然后将$a_{j,n-1-i}$旋转到$A_{1,1}$中的$a_{n-1-i,n-1-j}$，然后再将$A_{1,1}$中的$a_{n-1-i,n-1-j}$旋转到$A_{1,0}$中的$a_{n-1-j,i}$，最后将$a_{n-1-j,i}$旋转到$A_{0,0}$中的$a_{i,j}$。
在编程的时候对$a_{i,j}$,$a_{j,n-1-i}$,$a_{n-1-i,n-1-j}$,$a_{n-1-j,i}$这四个元素的4个旋转操作又可以替换为3个swap操作：
swap($a_{i,j}$,$a_{j,n-1-i}$);
swap($a_{i,j}$,$a_{n-1-j,i}$);
swap($a_{n-1-i,n-1-j}$,$a_{n-1-j,i}$);
对于n为奇数的情况，并不能像n为偶数那样直观地划分为4个小矩阵，而是去除矩阵中心的元素，将其余元素划分为旋转时互不相交的小矩形，比如将前$(n-1)/2$行、$(n+1)/2$列的元素作为$A_{0,0}$。其余的$A_{0,1}$，$A_{1,0}$,$A_{1,1}$的范围可以画图类推。
方法二
方法一是将整个矩阵划分成互不相交的4个区域，枚举其中一个区域来旋转。
方法二是同时对整个矩阵中的元素分步进行多次操作，最终达到将$a_{i,j}$变换到$a_{j,n-1-i}$的效果。
先对矩阵做沿主对角线的翻转(其实就是矩阵的转置)，原地完成，这个时候$a_{i,j}$变到了$a_{j,i}$；接着再对操作后的矩阵进行根据列序号倒排，于是$a_{j,i}$变到了$a_{j,n-1-i}$。综合两步来看就是将$a_{i,j}$变成了$a_{j,n-1-i}$。
延伸1 数组旋转
https://leetcode-cn.com/problems/rotate-array/
以leetcode这题为例，n个元素右移k位，
思路一
直接new新数组映射；$ a_{(i+k)mod \ n} = a_{i} $
思路二
通过右移k位这种操作，实际上是$a_{i}$，$a_{(i+k)mod\ n}$，$a_{(i+2k)mod\ n}$，$a_{(i+3k)mod\ n}$，这些元素形成了一个环，循环换了个位置。然后我们需要确定对给定的n和k，会形成多少个这样的环，这样我们才能确定需要枚举从$a_0$开始的多少个元素，然后对这些元素依次进行其所属环的循环位移操作。
显然，如果存在多个环，那么这些环里的元素个数是一样的，因此只需要分析$a_0$元素所属的环里有多少个元素。如leetcode官方题解所述，假设这个环里有b个元素，那么就有公式：$zn = bk$，即$a_0$元素经过b次右移同时也遍历数组z次后第一次重新回到了$a_0$的位置上。这个zn是n和k的倍数，同时z又是一个最小的使得zn是n和k的倍数的值，因此zn是n和k的最小公倍数，$zn=lcm(n,k)$，于是$b=lcm(n,k)/k$，于是环的个数为$n/b=n/(lcm(n,k)/k)=nk/lcm(n,k)=gcd(n,k)$。
因此只要枚举$a_0$到$a_{gcd(n,k)-1}$这些元素，对每个元素所在的环进行循环右移k位的操作就可以了。
思路三
右移k位这种操作，实际上是将前n-k个数移到了最后面，将后k个数移到了最前面，只是仍然保持原来的顺序。那么先将整个数组翻转，然后再对前k个数翻转，同时再对后n-k个数翻转，效果也是一样的。
延伸2 更一般的矩阵旋转
按照从外到内每个圈进行旋转就好了，具体的对于每个圈先将圈内的元素存入vector，然后利用vector对元素进行旋转，再将旋转后的元素放回矩阵即可。
void shiftLeft(vector<int> &arr, int steps) {
//cout << "shiftLeft " << arr.size() << " " << steps << endl;
steps = steps % arr.size();
vector<int> res(arr.size());
int len = arr.size();
for(int i = 0; i < len; i++) {
res[i] = arr[(i+steps) % len];
}
arr = res;
}
void rotateCircle(vector<vector<int>> &matrix, int depth, int row, int cols, int steps) {
//cout << "rotateCircle " << depth << " " << row << " " << cols << " " << steps << endl;
int start_r = depth;
int start_c = depth;
int len_c = cols - depth * 2;
int len_r = row - depth * 2;
vector<int> arr;
// upper edge
for(int i = 0; i < len_c; i++) {
arr.push_back(matrix[start_r][start_c + i]);
}
// right edge
for(int i = 0; i < len_r - 2; i++) {
arr.push_back(matrix[start_r + 1 + i][start_c + len_c - 1]);
}
// bottom edge
for(int i = len_c - 1; i >= 0; i--) {
arr.push_back(matrix[start_r + len_r - 1][start_c + i]);
}
// left edge
for (int i = len_r - 2; i >= 1; i--) {
arr.push_back(matrix[start_r + i][start_c]);
}
shiftLeft(arr, steps);
int index = 0;
// upper edge
for(int i = 0; i < len_c; i++) {
matrix[start_r][start_c + i] = arr[index++];
}
// right edge
for(int i = 0; i < len_r - 2; i++) {
matrix[start_r + 1 + i][start_c + len_c - 1] = arr[index++];
}
// bottom edge
for(int i = len_c - 1; i >= 0; i--) {
matrix[start_r + len_r - 1][start_c + i] = arr[index++];
}
// left edge
for (int i = len_r - 2; i >= 1; i--) {
matrix[start_r + i][start_c] = arr[index++];
}
}
void matrixRotation(vector<vector<int>> &matrix, int r) {
int rows = matrix.size();
int cols = matrix[0].size();
int layer = (rows > cols ? cols : rows) / 2;
for(int i = 0; i < layer; i++) {
rotateCircle(matrix, i, rows, cols, r);
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
近期评论