一幅由 N × N
矩阵表示的图像,其中每个像素的大小为 4 字节,将图像逆时针旋转 90 度。
给定 matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ], 使其变为 matrix = [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/rotate-matrix-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
图像旋转90度之后
matrix[0][0]变成了matrix_new[0][3];
matrix[1][0]变成了matrix_new[0][2];
matrix[1][1]变成了matrix_new[1][2];
matrix[1][2]变成了matrix_new[2][2];
可以得出结论——matrix_new[j][ matrixSize-1-i ]=matrix[i][j](得出的重要结论);
这里matrixSize表示数组的行高,i表示行,j表示列。
重要结论——matrix_new[ j ][ matrixSize-1-i ]=matrix[ i ][ j ]
方法一
借助辅助数组——辅助数组来存储旋转后的图像,之后再将辅助数组所存储的图像赋给原来的数组,达到目的,这个方法简单,但是需要开辟一个新的空间。
void rotate(int** matrix, int matrixSize, int* matrixColSize) {
int matrix_new[matrixSize][matrixSize];
for (int i = 0; i < matrixSize; i++) {
for (int j = 0; j < matrixSize; j++) {
matrix_new[i][j] = matrix[i][j];
}
}
for (int i = 0; i < matrixSize; ++i) {
for (int j = 0; j < matrixSize; ++j) {
matrix[j][matrixSize - i - 1] = matrix_new[i][j];
}
}
}
方法二
原地旋转图像——旋转一次图像的话
matrix[i][j]移动到了matrix[j][matrixSize-1-i];
matrix[j][matrixSize-1-i]移动到了matrix[n−row−1][n−col−1];
matrix[n−row−1][n−col−1]移动到了matrix[j][matrixSize - i - 1];
matrix[j][matrixSize - i - 1]移动到了matrix[i][j];
每次旋转都会交换四个位置,
当matrixSize 为偶数时需要进行(matrixSize)^2 / 4 = (matrixSize/2) * (matrixSize/2) 次旋转;
当matrixSize为奇数时,中心位置无需旋转,需要进行(matrixSize^2−1)/4 = ((matrixSize−1)/2)×((matrixSize+1) / 2) 次旋转;
由于没有引入辅助数组,旋转之后的数据会覆盖之前的数据,防止数据被覆盖,引入一个新的变量
void rotate(int** matrix, int matrixSize, int* matrixColSize) {
for (int i = 0; i < matrixSize / 2; ++i) {
for (int j = 0; j < (matrixSize + 1) / 2; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[matrixSize - j - 1][i];
matrix[matrixSize - j - 1][i] = matrix[matrixSize - i - 1][matrixSize - j - 1];
matrix[matrixSize - i - 1][matrixSize - j - 1] = matrix[j][matrixSize - i - 1];
matrix[j][matrixSize - i - 1] = temp;
}
}
}
方法三
图像反转代替图像原地旋转
上下水平反转得到
[ [ [ 5, 1, 9,11], [15 14 12 16] [ 2, 4, 8,10], ——> [13 3 6 7 ] [13, 3, 6, 7], [2 4 8 10] [15,14,12,16] [5 1 9 11] ] ]
主对角线反转得到
[ [ [15 14 12 16] [15 13 2 5] [13 3 6 7 ] ——> [14 3 4 1] [2 4 8 10] [12 6 8 9] [5 1 9 11] [16 7 10 11] ] 如果是顺时针旋转的话,应该是先进行主对角线反转,再进行水平反转来达到目的 ]
void swap(int* a, int* b) {
int t = *a;
*a = *b, *b = t;
}
void rotate(int** matrix, int matrixSize, int* matrixColSize) {
// 水平翻转
for (int i = 0; i < matrixSize / 2; ++i) {
for (int j = 0; j < matrixSize; ++j) {
swap(&matrix[i][j], &matrix[matrixSize - i - 1][j]);
}
}
// 主对角线翻转
for (int i = 0; i < matrixSize; ++i) {
for (int j = 0; j < i; ++j) {
swap(&matrix[i][j], &matrix[j][i]);
}
}
}